1 条题解

  • 0
    @ 2021-6-15 14:28:44

    C++ :

    #include<cstdio>
    #include<cmath>
    #include<set>
    #include<map>
    #include<algorithm>
    using namespace std;
    const double eps=1e-8;
    const int N=20010,M=50010;
    int n,m,q,cnt,i,x,y;
    map<int,int>T[20010];
    inline int sgn(double x){
      if(fabs(x)<eps)return 0;
      return x>0?1:-1;
    }
    struct P{
      double x,y;
      P(){}
      P(double _x,double _y){x=_x,y=_y;}
      double operator*(const P&b){return x*b.y-y*b.x;}
    }a[N],b[N];
    struct E{
      int x,y;double o;
      E(){}
      E(int _x,int _y){x=_x,y=_y,o=atan2(a[y].x-a[x].x,a[y].y-a[x].y);}
    }e[M];
    bool del[M],ex[M];int from[M],id[N],f[N];
    struct EV{
      double x;int y,t;
      EV(){}
      EV(double _x,int _y,int _t){x=_x,y=_y,t=_t;}
    }ev[M<<1];
    inline bool cmpEV(const EV&a,const EV&b){
      if(sgn(a.x-b.x))return a.x<b.x;
      return a.t<b.t;
    }
    namespace GetArea{
    struct cmp{bool operator()(int a,int b){return e[a].o<e[b].o;}};
    set<int,cmp>g[N];set<int,cmp>::iterator k;int i,j,q[M],t;
    void work(){
      for(i=0;i<m+m;i++)if(!del[i]&&!ex[i]){
        for(q[t=1]=j=i;;q[++t]=j=*k){
          k=g[e[j].y].find(j^1);k++;
          if(k==g[e[j].y].end())k=g[e[j].y].begin();
          if(*k==i)break;
        }
        double s=0;
        for(j=1;j<=t;j++)s+=a[e[q[j]].x]*a[e[q[j]].y],del[q[j]]=1;
        if(sgn(s)<0)continue;
        for(cnt++,j=1;j<=t;j++)from[q[j]]=cnt;
      }
    }
    }
    namespace ScanLine{
    struct cmp{
      bool operator()(int A,int B){
        if(e[A].x==e[B].x)return e[A].o>e[B].o;
        double x=min(a[e[A].x].x,a[e[B].x].x),
               yA=(a[e[A].x].y-a[e[A].y].y)*(x-a[e[A].y].x)/(a[e[A].x].x-a[e[A].y].x)+a[e[A].y].y,
               yB=(a[e[B].x].y-a[e[B].y].y)*(x-a[e[B].y].x)/(a[e[B].x].x-a[e[B].y].x)+a[e[B].y].y;
        return yA>yB;
      }
    };
    set<int,cmp>T;
    int cnt,i,j,k,g[M],v[M],nxt[M],ed,vis[N],t,tmp[N];
    inline bool cmpC(int x,int y){return a[x].x<a[y].x;}
    inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
    void dfs(int x){
      vis[x]=1;
      if(a[x].y>a[t].y)t=x;
      for(int i=g[x];i;i=nxt[i])if(!vis[v[i]])dfs(v[i]);
    }
    inline double cal(int A,double x){
      return(a[e[A].x].y-a[e[A].y].y)*(x-a[e[A].y].x)/(a[e[A].x].x-a[e[A].y].x)+a[e[A].y].y;
    }
    void connect(){
      for(i=0;i<m+m;i++)add(e[i].x,e[i].y);
      for(i=1;i<=n;i++)if(!vis[i])dfs(t=i),ev[cnt++]=EV(a[t].x,t,2);
      for(i=0;i<m+m;i++)if(sgn(a[e[i].x].x-a[e[i].y].x)>0){
        ev[cnt++]=EV(a[e[i].y].x,i,1);
        ev[cnt++]=EV(a[e[i].x].x,i,0);
      }
      sort(ev,ev+cnt,cmpEV);
      a[n+1]=P(10010,10010);
      a[n+2]=P(-10010,10010);
      e[m+m]=E(n+1,n+2);
      T.insert(m+m);
      e[m+m+1]=E(n+2,n+1);
      n+=2,m++;
      for(ed=0,i=1;i<=n;i++)g[i]=0;
      for(i=0;i<cnt;i++){
        if(ev[i].t==0)T.erase(ev[i].y);
        if(ev[i].t==1)T.insert(ev[i].y);
        if(ev[i].t==2){
          a[n+1]=P(ev[i].x,a[ev[i].y].y+eps);
          a[n+2]=P(ev[i].x-1,a[ev[i].y].y+eps);
          e[m+m]=E(n+1,n+2);
          T.insert(m+m);
          set<int,cmp>::iterator j=T.find(m+m);
          j--,add(*j,ev[i].y);
          T.erase(m+m);
        }
      }
      int newm=m+m;
      for(i=0;i<m+m;i++){
        for(cnt=0,j=g[i];j;j=nxt[j]){
          if(!sgn(a[v[j]].x-a[e[i].x].x)){
            e[newm++]=E(v[j],e[i].x);
            e[newm++]=E(e[i].x,v[j]);
            continue;
          }
          if(!sgn(a[v[j]].x-a[e[i].y].x)){
            e[newm++]=E(v[j],e[i].y);
            e[newm++]=E(e[i].y,v[j]);
            continue;
          }
          tmp[++cnt]=v[j];
        }
        if(!cnt)continue;
        ex[i]=ex[i^1]=1;
        sort(tmp+1,tmp+cnt+1,cmpC);
        for(k=e[i].y,j=1;j<=cnt;k=n,j++){
          a[++n]=P(a[tmp[j]].x,cal(i,a[tmp[j]].x));
          e[newm++]=E(k,n);
          e[newm++]=E(n,k);
          e[newm++]=E(tmp[j],n);
          e[newm++]=E(n,tmp[j]);
        }
        e[newm++]=E(n,e[i].x);
        e[newm++]=E(e[i].x,n);
      }
      m=newm/2;
    }
    void location(){
      for(i=cnt=0;i<m+m;i++)if(!ex[i]&&sgn(a[e[i].x].x-a[e[i].y].x)>0){
        ev[cnt++]=EV(a[e[i].y].x,i,1);
        ev[cnt++]=EV(a[e[i].x].x,i,0);
      }
      for(i=0;i<q;i++)ev[cnt++]=EV(b[i].x,i,2);
      sort(ev,ev+cnt,cmpEV);
      T.clear();
      for(i=0;i<cnt;i++){
        if(ev[i].t==0)T.erase(ev[i].y);
        if(ev[i].t==1)T.insert(ev[i].y);
        if(ev[i].t==2){
          a[n+1]=P(ev[i].x,b[ev[i].y].y);
          a[n+2]=P(ev[i].x-1,b[ev[i].y].y);
          e[m+m]=E(n+1,n+2);
          T.insert(m+m);
          set<int,cmp>::iterator j=T.find(m+m);
          if(j!=T.begin())j--,id[ev[i].y]=from[*j];
          T.erase(m+m);
        }
      }
    }
    }
    inline int getid(){
      int x,y;
      scanf("%d%d",&x,&y);
      if(T[x+10000][y])return T[x+10000][y];
      T[x+10000][y]=++n;
      a[n]=P(x,y);
      return n;
    }
    bool g[610][610];
    int main(){
      scanf("%d%d",&q,&m);
      for(i=0;i<q;i++)scanf("%lf%lf",&b[i].x,&b[i].y);
      for(i=0;i<m;i++){
        x=getid();
        y=getid();
        e[i<<1]=E(x,y);
        e[i<<1|1]=E(y,x);
      }
      ScanLine::connect();
      for(i=0;i<m+m;i++)if(!ex[i])GetArea::g[e[i].x].insert(i);
      GetArea::work();
      ScanLine::location();
      for(i=0;i<q;i++)f[id[i]]=i+1;
      for(i=0;i<m+m;i++)if(!ex[i])g[f[from[i]]][f[from[i^1]]]=1;
      for(i=1;i<=q;i++){
        for(x=g[i][i]=0,y=1;y<=q;y++)if(g[i][y])x++;
        printf("%d",x);
        for(y=1;y<=q;y++)if(g[i][y])printf(" %d",y);
        puts("");
      }
      return 0;
    }
    
    • 1

    信息

    ID
    1005
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者