loj提交记录

darkbzoj提交记录

精度真的玄学

我裂开啦

#include<cstdio>
#include<algorithm>
#include<cmath>
#define reg register
#define vec(x,y) ((vec){x,y})
#define ray(a,b) ((ray){a,b})
const int MaxN=300000;
typedef long double ldb;
const ldb eps=1e-14;
template<typename num>inline void read(num &ans)
{
	ans=0;
	int sign=0;
	char c=getchar();
	while((c<'0'||c>'9')&&c!='-')
		c=getchar();
	if(c=='-')
		sign=1,c=getchar();
	while(c>='0'&&c<='9')
		ans=ans*10+c-48,c=getchar();
	ans=sign?-ans:ans;
	return;
}
struct vec
{
	ldb x,y;
	inline vec operator + (const vec &b) const {return (vec){x+b.x,y+b.y};}
	inline vec operator - (const vec &b) const {return (vec){x-b.x,y-b.y};}
	inline vec operator * (const ldb &k) const {return (vec){x*k,y*k};}
	inline ldb operator ^ (const vec &b) const {return x*b.y-y*b.x;}
	inline bool left(const vec &b) const {return (*this^b)>eps;}
	inline bool right(const vec &b) const {return (*this^b)<-eps;}
};
struct ray
{
	vec x,v;
	ldb ag;
	inline bool left(const vec &b) const {return v.left(b-x);}
	inline bool right(const vec &b) const {return v.right(b-x);}
};
inline ldb abslute(const ldb &x)
{
	return x<0?-x:x;
}
inline vec crosspoint(vec a,vec b,vec c,vec d)
{
	ldb s1=(b-a)^(c-a),s2=(b-a)^(d-a);
	return c+(c-d)*(s1/(s2-s1));
}
inline vec crosspoint(ray a,ray b)
{
	return crosspoint(a.x,a.x+a.v,b.x,b.x+b.v);
}
inline ray calc(ray a,ray b)
{
	if(abslute(a.v^b.v)<eps)
		return ray((a.x+b.x)*0.5,b.v);
	vec c=crosspoint(a,b);
	return ray(c,crosspoint(ray(a.x+b.v,a.v),ray(b.x-a.v,b.v))-c);
}
inline bool cmp(const ray &a,const ray &b)
{
	return a.ag<b.ag;
}
int n;
vec a[MaxN+1];
ray r[MaxN+1],q[MaxN+1];
int h,t;
inline bool check_pop(ray a,ray b,ray c)
{
//	return abslute(a.v^b.v)>eps&&
	return (!c.left(crosspoint(a,b)));
}
void fuck(int n)
{
	for(reg int i=1;i<=n;++i)
		r[i].ag=atan2(r[i].v.y,r[i].v.x);
	std::sort(r+1,r+n+1,cmp);
	int cnt=0;
	for(reg int i=1;i<=n;++i)
		if(cnt&&abslute(r[cnt].ag-r[i].ag)<eps)
			r[cnt]=r[cnt].left(r[i].x)?r[i]:r[cnt];
		else
			r[++cnt]=r[i];	
	h=1,t=0;
	for(reg int i=1;i<=cnt;++i)
	{
		while(h<t&&check_pop(q[t-1],q[t],r[i]))
			--t;
		while(h<t&&check_pop(q[h+1],q[h],r[i]))
			++h;
		q[++t]=r[i];
	}
	while(h+1<t&&check_pop(q[t-1],q[t],q[h]))
		--t;
	return;
}
vec p[MaxN+1];
int main()
{
	int cnt=0;
	ldb tot=0;
	read(n);
	for(reg int i=1;i<=n;++i)
		read(a[i].x),read(a[i].y);
	for(reg int i=2;i<n;++i)
		tot+=((a[i]-a[1])^(a[i+1]-a[1]));
	for(reg int i=1;i<n;++i)
		r[++cnt]=ray(a[i],a[i+1]-a[i]);
	r[++cnt]=ray(a[n],a[1]-a[n]);
	for(reg int i=2;i<n;++i)
		r[++cnt]=calc(ray(a[1],a[2]-a[1]),ray(a[i],a[i+1]-a[i]));
	r[++cnt]=calc(ray(a[1],a[2]-a[1]),ray(a[n],a[1]-a[n]));
	fuck(cnt);
	cnt=0;
	for(reg int i=h;i<t;++i)
		if(abslute(q[i].v^q[i+1].v)>eps)
			p[++cnt]=crosspoint(q[i],q[i+1]);
	if(abslute(q[t].v^q[h].v)>eps)
		p[++cnt]=crosspoint(q[t],q[h]);
	ldb ans=0;
	for(reg int i=2;i<cnt;++i)
		ans+=((p[i]-p[1])^(p[i+1]-p[1]));
	printf("%.4lf\n",double(ans/tot));
	return 0;
}