题解：CF1158D Winding polygonal line

计算几何。

考虑凸包。限定一条边作为起始边（假设他是顺时针，逆时针相反），发现怎么走都相当于 R。

同时，我们删除走过的点，对新的点集维护凸包，我们只在凸包上移动。

不难发现，上一步是顺时针，这一步就是 R，反之是 L。

我们根据下一步的符号决定在凸包上移动的方向即可。

通过 ~~OI-WIKI~~ Andrew 法，我们可以

O(n\log{n})

求出凸包。所以这玩意是

O(n^2\log{n})

的。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
struct node{int x,y;}p[2005];
node operator+(node a,node b){return {a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return {a.x-b.x,a.y-b.y};}
int operator*(node a,node b){return a.x*b.y-a.y*b.x;}
int r[2005];
bool cmp(int x,int y){
    if(x==n+1||y==n+1)return x<y;
    if(p[x].x!=p[y].x)return p[x].x<p[y].x;
    return p[x].y<p[y].y;
}
int stk[2005],tot,in[2005],lpt[2005],rpt[2005];
void upd(){
    sort(r+1,r+1+n,cmp);
    for(int i=1;i<=n;i++)in[i]=0;
    tot=0;
    stk[++tot]=r[1];
    for(int i=2;i<=m;i++){
        while(tot>1&&(p[stk[tot]]-p[stk[tot-1]])*(p[r[i]]-p[stk[tot]])<=0)in[stk[tot--]]=0;
        stk[++tot]=r[i];
        in[r[i]]=1;
    }
    int tmp=tot;
    for(int i=m-1;i>=1;i--){
        if(in[r[i]])continue;
        while(tot-tmp>0&&(p[stk[tot]]-p[stk[tot-1]])*(p[r[i]]-p[stk[tot]])<=0)in[stk[tot--]]=0;
        stk[++tot]=r[i];
        in[r[i]]=1;
    }
    tot--;
    lpt[stk[1]]=stk[tot];
    rpt[stk[1]]=stk[2];
    lpt[stk[tot]]=stk[tot-1];
    rpt[stk[tot]]=stk[1];
    for(int i=2;i<tot;i++){
        lpt[stk[i]]=stk[i-1];
        rpt[stk[i]]=stk[i+1];
    }
}
vector<int> ans;
char s[2005];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;m=n;
    for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y,r[i]=i;
    upd();
    int now=r[1];ans.push_back(now);
    cin>>(s+2);
    for(int i=2;i<=n;i++){
        int lst=now;
        if(s[i]=='L')now=rpt[now];
        else now=lpt[now];
        ans.push_back(now);
        for(int j=1;j<=m;j++)if(r[j]==lst)r[j]=n+1;
        m--;
        upd();
    }
    for(auto ed:ans)cout<<ed<<' ';
}

题解：CF1158D Winding polygonal line

文章操作

相关推荐

评论

题解：CF1158D Winding polygonal line