[2019牛客多校第二场][G. Polygons]

题目链接：https://ac.nowcoder.com/acm/contest/882/G

题目大意：有\(n\)条直线将平面分成若干个区域，要求处理\(m\)次询问：求第\(q\)大的区域面积。保证没有三线共点或者两直线重合，\(n\leq 1000,\ m\leq 10000\)

题解：先考虑最多会有多少个区域，由于第\(i\)条直线最多与前面的\(i-1\)条直线同时相交，所以交点个数和区域个数都是\(n^2\)级别的，考虑求出所有区域的面积并排序

　　　首先预处理所有的交点，并记录与该交点相邻的交点，在他们之间建两条有向边（即记录两个向量）。由于没有三线共点的情况，所以每个点的度数均不超过\(4\)。每次选取一个点作为起点，并选取另一个与之相邻的点作为当前点，从当前点出发寻找一个没被使用过且与当前边的向量夹角最大（或最小）的边，并进入下一个点，直至回到原点。这样就能找出其中的一个区域。执行这样的算法若干次直至所有边均被使用过就能求出所有的区域面积，注意判断当前区域不合法的情况即可。

　　　关于为什么每次找夹角最大（或最小）的边能找到所有区域，是因为这个过程实际上是平面图转对偶图的算法实现（具体见http://blog.miskcoo.com/2015/05/planar-graph-dual-and-point-locate 这篇博客的讲解，感谢qls深夜给我普及这一知识点），因此如果每次找夹角最小的边是显然正确的。关于找夹角最大的正确性我想是因为，由于每个交点最多是两条直线的交点，所以最小角和最大角的区别就是左转和右转，也是满足这一算法的要求的。

　　　对于这题的代码实现，我的做法是对于每条直线先预处理所有交点坐标并排好序（可以用点乘实现），然后就可以处理出和每个交点相邻的点是哪几个。由于每次只可能有两个合法的相邻点，所以可以直接用叉积的正负来判断下一个要走哪个点，剩下的就是判断合法性的问题了

 #include<bits/stdc++.h>

 using namespace std;

 #define N 1001

 #define mp make_pair

 const double eps=1e-;

 int n,m,q,cnt,f[N*N],poly[N];

 vector<pair<int,bool>>d[N*N];

 vector<pair<double,int>>l[N];

 vector<double>ans;

 struct Point

 {

     double x,y;

     void read(){scanf("%lf%lf",&x,&y);}

     Point operator +(const Point &t)const{return {x+t.x,y+t.y};}

     Point operator -(const Point &t)const{return {x-t.x,y-t.y};}

     double operator *(const Point &t)const{return x*t.y-y*t.x;}

     double operator %(const Point &t)const{return x*t.x+y*t.y;}

     Point operator *(double t)const{return {x*t,y*t};}

     Point operator /(double t)const{return {x/t,y/t};}

 }p[N*N];

 struct Line

 {

     Point p1,p2;

     void read(){p1.read(),p2.read();}

     bool intersect(const Line &t)const

       {return fabs((p2-p1)*(t.p2-t.p1))>eps;}

     Point isct(const Line &t)const

       {

       double a=(p2-p1)*(t.p1-p1);

       double b=(p2-p1)*(p1-t.p2);

       return (t.p1*b+t.p2*a)/(a+b);

       }

 }a[N];

 void del(int st,int ed)

 {

     for(int i=;i<d[st].size();i++)

       if(d[st][i].first==ed)

         {

         d[st][i].second=false;

         f[st]--;

         return;

         }

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

       a[i].read();

     for(int i=;i<=n;i++)

       for(int j=i+;j<=n;j++)

         if(a[i].intersect(a[j]))

           {

           p[++cnt]=a[i].isct(a[j]);

           l[i].push_back(mp((p[cnt]-a[i].p1)%(a[i].p2-a[i].p1),cnt));

           l[j].push_back(mp((p[cnt]-a[j].p1)%(a[j].p2-a[j].p1),cnt));

           }

     for(int i=;i<=n;i++)

       {

       sort(l[i].begin(),l[i].end());

       for(int j=;j<l[i].size();j++)

         {

         d[l[i][j].second].push_back(mp(l[i][j-].second,true));

         d[l[i][j-].second].push_back(mp(l[i][j].second,true));

         f[l[i][j].second]++;

         f[l[i][j-].second]++;

         }

       }

     for(int i=;i<=cnt;i++)

       while(f[i])

         {

         int pcnt=,st=i,pre=i,cur=-;

         poly[++pcnt]=st;

         for(auto pi:d[st])

           if(pi.second)

             {

             cur=poly[++pcnt]=pi.first;

             break;

             }

         while(cur!=st)

           {

           int id=-;double mx=-1.0;

           for(auto pi:d[cur])

             if(pi.second)

               {

               int nxt=pi.first;

               if(nxt==pre)continue;

               double tmp=(p[cur]-p[pre])*(p[nxt]-p[cur]);

               if(tmp>mx)mx=tmp,id=nxt;

               }

           if(id< || mx<eps)

             {

             for(int i=;i<pcnt;i++)

               del(poly[i],poly[i+]);

             pcnt=;

             break;

             }

           poly[++pcnt]=id;

           pre=cur,cur=id;

           }

         if(!pcnt)continue;

         double res=;

         for(int i=;i<=pcnt;i++)

           {

           res+=p[poly[i]]*p[poly[i%pcnt+]];

           del(poly[i],poly[i%pcnt+]);

           }

         res*=0.5;

         ans.push_back(fabs(res));

         }

     sort(ans.begin(),ans.end());

     int sz=ans.size();

     printf("%d %.6f %.6f\n",sz,ans[sz-],ans[]);

     scanf("%d",&m);

     while(m--)

       {

       scanf("%d",&q);

       if(q>sz){printf("Invalid question\n");continue;}

       printf("%.6f\n",ans[sz-q]);

       }

 }

巴特西

[2019牛客多校第二场][G. Polygons]

最新文章

热门文章