「SCOI2015」小凸想跑步 https://loj.ac/problem/2008
最开始以为和多边形的重心有关, 后来发现多边形的重心没啥好玩的性质
实际上你把面积小于的不等式列出来, 发现是一次的, 那么就可以半平面交了
- Code:
- #include
- #include
- #include
- #define Vector Point
- const int N=2e5+10;
- const double eps=1e-7;
- int n,m,l,r;
- struct Point
- {
- double x,y;
- Point(){}
- Point(double X,double Y){x=X,y=Y;}
- double angle(){return atan2(y,x);}
- Vector friend operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
- Vector friend operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
- Vector friend operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}
- }bee[N],q1[N];
- struct Line
- {
- Point s,t;double ang;
- Line(){}
- Line(Point S,Point T){s=S,t=T,ang=(t-s).angle();}
- }yuu[N],q2[N];
- double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
- bool isrig(Line a,Point b){return Cross(b-a.s,a.t-a.s)>0;}
- bool cmp(Line a,Line b){return fabs(a.ang-b.ang)<eps?isrig(a,b.t):a.ang<b.ang;}
- Point jd(Line a,Line b){return a.s+(a.t-a.s)*(Cross(a.s-b.s,b.t-b.s)/Cross(b.t-b.s,a.t-a.s));}
- void SI()
- {
- std::sort(yuu+1,yuu+1+m,cmp);
- q2[l=r=1]=yuu[1];
- for(int i=2;i<=m;i++)
- if(fabs(yuu[i].ang-yuu[i-1].ang)>eps)
- {
- while(l<r&&isrig(yuu[i],q1[r-1])) --r;
- while(l<=r&&isrig(yuu[i],q1[l])) ++l;
- q1[r]=jd(q2[r],yuu[i]);
- q2[++r]=yuu[i];
- }
- while(l<r&&isrig(q2[l],q1[r-1])) --r;
- q1[r]=jd(q2[l],q2[r]);
- }
- double area()
- {
- if(r-l<2) return 0;
- double ret=0;
- for(int i=l;i<r;i++) ret+=Cross(q1[i],q1[i+1]);
- ret+=Cross(q1[r],q1[l]);
- return ret/2;
- }
- int main()
- {
- scanf("%d",&n);m=n;double sum=0;
- for(int i=1;i<=n;i++)
- {
- scanf("%lf%lf",&bee[i].x,&bee[i].y);
- yuu[i]=Line(bee[i-1],bee[i]);
- if(i!=1) sum+=Cross(bee[i-1],bee[i]);
- }
- yuu[1]=Line(bee[n],bee[1]);
- sum+=Cross(bee[n],bee[1]);
- sum/=2;
- bee[++n]=bee[1];
- for(int i=3;i<=n;i++)
- {
- double A=bee[1].y-bee[2].y-(bee[i-1].y-bee[i].y);
- double B=bee[2].x-bee[1].x-(bee[i].x-bee[i-1].x);
- double C=Cross(bee[1],bee[2])-Cross(bee[i-1],bee[i]);
- if(fabs(A)<eps) yuu[++m]=Line(Point(0,-C/B),Point(0,-C/B)+Vector(-B,A));
- else yuu[++m]=Line(Point(-C/A,0),Point(-C/A,0)+Vector(-B,A));
- }
- SI();
- printf("%.4f\n",area()/sum);
- return 0;
- }
- 2019.3.4
来源: http://www.bubuko.com/infodetail-2975280.html