「SCOI2015」小凸想跑步 解题报告

「SCOI2015」小凸想跑步

最开始以为和多边形的重心有关，后来发现多边形的重心没啥好玩的性质

实际上你把面积小于的不等式列出来，发现是一次的，那么就可以半平面交了

---

Code:

#include <cstdio>

#include <cmath>

#include <algorithm>

#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