C++ 解法, 执行用时: 481ms, 内存消耗: 35692K, 提交时间: 2022-03-27 14:17:03

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
using ldouble=long double;
const ldouble e=1e-10;
#define SI static inline
SI int tri_compare(ldouble x) {return fabs(x)<=e?0:x>e?1:-1;}
struct Point {
	ldouble x,y;
};
#define x1 A.x
#define y1 A.y
#define x2 B.x
#define y2 B.y
SI Point operator+(Point A, Point B){ return {x1+x2,y1+y2}; }
SI Point operator-(Point A, Point B){ return {x1-x2,y1-y2}; }
SI Point operator*(ldouble K, Point A){ return {K*x1,K*y1}; }
SI Point Vec(Point A, Point B){ return B-A; } /// gai
SI ldouble dot  (Point A, Point B){ return x1*x2 + y1*y2; }
SI ldouble cross(Point A, Point B){ return x1*y2 - x2*y1; }
#undef x1
#undef x2
#undef y1
#undef y2

struct Line {
	Point A;
	Point B;
	ldouble Arg=100;
	Point vec(){ return Vec(A,B); } // v
	ldouble arg(){
		if(Arg<50) return Arg;
		return Arg=atan2(vec().y,vec().x);
	}
};
SI bool operator<(Line m, Line n){ return m.arg()<n.arg(); }

SI bool OnLeft(Line L, Point A){ return tri_compare(cross(L.vec(),Vec(L.A,A)))>=0; }

SI Point intersection(Line a,Line b) {
    Point u=Vec(a.A,b.A);
    ldouble t=cross(u,b.vec())/cross(a.vec(),b.vec());
    return a.A+t*a.vec();
}

ldouble Area(Point* A, int n)
{
	ldouble ans=0;
	for(int i=0; i<n; i++) ans+=cross(A[i],A[(i+1)%n]);
	return ans/2;
}

int HalfplaneIntersection(Line* L, int n, Point* poly)
{
	stable_sort(L,L+n);
	int first=0,last=0;
	static Point p[maxn];
	static Line q[maxn+5];
	q[last]=L[0];
	for(int i=1; i<=n; i++) {
		while(first<last&&!OnLeft(L[i],p[last-1]))last--;
		while(first<last&&!OnLeft(L[i],p[first]))first++;
		q[++last]=L[i];
		if(first<last)p[last-1]=intersection(q[last-1],q[last]);
	}
	while(first<last&&!OnLeft(q[first],p[last-1]))last--;
	if(last-first<=1)return 0;
	p[last]=intersection(q[last],q[first]);
	int m=0;
	for(int i=first; i<=last; i++) poly[m++]=p[i];
	return m;
}
Point A[maxn],ans[maxn];
Line L[maxn];
int main() {
	int n,cnt=0;
	scanf("%d",&n);
	for(int i=0; i<n; i++) {
		scanf("%Lf",&A[i].x);
		scanf("%Lf",&A[i].y);
	}
	A[n]=A[0];
	for(int i=0; i<n; i++)L[cnt++]={A[i],A[i+1]};
	for(int i=1; i<n; i++) {
		ldouble a=A[1].y-A[0].y-A[i+1].y+A[i].y,b=A[0].x-A[1].x-A[i].x+A[i+1].x,c=A[1].x*A[0].y-A[0].x*A[1].y-A[i+1].x*A[i].y+A[i].x*A[i+1].y;
		if(tri_compare(b)) L[cnt++]={{0,-c/b},{b,-a-c/b}};
		else if(tri_compare(a)) L[cnt++]={{-c/a,0},{-c/a,-a}};
	}
	int tot=HalfplaneIntersection(L,cnt,ans);
	printf("%0.4Lf\n",Area(ans,tot)/Area(A,n));
}