2019 牛客多校G Polygons

题意:问n条直线交出来的所有多边形的面积。

最左转线法求平面区域的模板题。在WC2013平面图前就是个弟弟。

  1. /*
  2. Author: fffasttime
  3. Date: 2019/07/27 21:00
  4.  */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. typedef long long ll;
  8. #define inc(i,n) for (int i=0;i<n;i++)
  9. const int N=1010;
  10. typedef double db;
  11. const db eps=1e-10;
  12. bool eq(db x){return fabs(x)<eps;}
  13. struct vec{
  14.     db x,y;
  15.     vec operator-(const vec &v)const{return {x-v.x,y-v.y};}
  16.     vec operator+(const vec &v)const{return {x+v.x,y+v.y};}
  17.     vec operator*(db t)const{return {x*t,y*t};}
  18.     bool operator<(const vec &v) const{return eq(x-v.x)?y<v.y:x<v.x;}
  19.     db operator&(const vec &v)const{return x*v.y-y*v.x;}
  20.     void rd(){scanf("%lf%lf",&x,&y);}
  21.     //void rd(){x=rand()%1000; y=rand()%1000;}
  22.     db ang()const{return atan2(y,x);}
  23. }p[N*N*2],l1[N],l2[N];//p[n..n+2q] used for question
  24.  
  25. const db pi=acos(-1);
  26.  
  27. struct Edge{ //main transfer structure
  28.     db ang; int u,v,w; bool vis;
  29.     int rk;
  30.     int fr;
  31.     Edge(){}
  32.     Edge(int u, int v, int w):u(u),v(v){
  33.         ang=(p[v]-p[u]).ang();
  34.         rk=fr=0;
  35.         vis=0;
  36.     }
  37.     bool operator<(const Edge &v)const{return ang<v.ang;}
  38. }ed[N*N*4];
  39. int edc=1,gcnt=0;
  40.  
  41. vector<int> ed1[N*N];
  42. vector<int> linep[N];
  43. db ans[N*N*2]; int ansc;
  44. vec lineInt(vec p, vec vp, vec q, vec vq){
  45.     db t=(vq & p-q)/(vp&vq);
  46.     return p+vp*t;
  47. }
  48. int main(){
  49.     int n0; scanf("%d",&n0);
  50.     int n=0;
  51.     inc(i,n0){
  52.         l1[i].rd(); l2[i].rd();
  53.         inc(j,i) if (!eq((l2[i]-l1[i]&l2[j]-l1[j]))){
  54.             p[n]=lineInt(l1[i],l2[i]-l1[i],l1[j],l2[j]-l1[j]);
  55.             linep[i].push_back(n);
  56.             linep[j].push_back(n);
  57.             n++;
  58.         }
  59.     }
  60.     inc(i,n0){
  61.         sort(linep[i].begin(),linep[i].end(),[&](int x, int y){return p[x]<p[y];});
  62.         for (int j=0;j<linep[i].size()-1;j++){
  63.             int x=linep[i][j], y=linep[i][j+1];
  64.             ed[++edc]=Edge(x,y,0);
  65.             ed1[x].push_back(edc);
  66.             ed[++edc]=Edge(y,x,0);
  67.             ed1[y].push_back(edc);
  68.         }
  69.     }
  70.     inc(i,n){
  71.         sort(ed1[i].begin(),ed1[i].end(),[&](int a, int b){return ed[a].ang<ed[b].ang;});
  72.         inc(j,ed1[i].size())
  73.             ed[ed1[i][j]].rk=j;
  74.     }
  75.     int gout;
  76.     for (int i=2;i<=edc;i++) if(!ed[i].vis){ //new
  77.         int u=ed[i].u; int cur=i;
  78.         gcnt++;
  79.         db area=0;
  80.         while (!ed[cur].vis){ //face
  81.             ed[cur].fr=gcnt;
  82.             ed[cur].vis=1;
  83.             area+=(p[ed[cur].u]-p[u])&(p[ed[cur].v]-p[u]);
  84.             int sz=ed1[ed[cur].v].size();
  85.             int rk1=(ed[cur^1].rk-1+sz)%sz;
  86.             cur=ed1[ed[cur].v][rk1];
  87.         }
  88.         if (area<=0) gout=gcnt;
  89.         else ans[ansc++]=area/2;
  90.     }
  91.     sort(ans,ans+ansc,greater<db>());
  92.     printf("%d %.6f %.6f\n",ansc,ans[0],ans[ansc-1]);
  93.     int q; scanf("%d",&q);
  94.     while (q--){
  95.         int t; scanf("%d",&t);t--;
  96.         if (t>=ansc) puts("Invalid question");
  97.         else printf("%.6f\n",ans[t]);
  98.     }
  99.     return 0;
  100. }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注