80分,wa5 7,调了一下午一晚上了,救命……
查看原帖
80分,wa5 7,调了一下午一晚上了,救命……
536337
eb0ycn楼主2024/4/26 21:44
#include<bits/stdc++.h>
using namespace std;
int n,m,l=-1,r=-1,q[502],cnt,la;
double ans,s1,s2;
int sgn(double x){
	if(fabs(x)<1e-8)return 0;
	return x>0?1:-1;
}
struct node{
	double x,y;
	double operator*(const node&cwx)const{return {x*cwx.y-y*cwx.x};}
	node operator*(const double&cwx)const{return {x*cwx,y*cwx};}
	node operator-(const node&cwx)const{return {x-cwx.x,y-cwx.y};}
	node operator+(const node&cwx)const{return {x+cwx.x,y+cwx.y};}
}p[501],d[502];
struct line{
	node s,t;
	double art;
	line(){}
	line(node a,node b){s=a,t=b,art=atan2(b.y-a.y,b.x-a.x);}
	bool operator<(const line&cwx)const{return sgn(art-cwx.art)?art<cwx.art:(t-s)*(cwx.s-s)<-1e-8;}
}e[501];
node get(line a,line b){
	s1=(b.t-a.s)*(a.t-a.s),s2=(b.s-a.s)*(a.t-a.s);
	return {(b.s.x*s1-b.t.x*s2)/(s1-s2),(b.s.y*s1-b.t.y*s2)/(s1-s2)};
}
int main(){
	scanf("%d",&n);
	while(n--){
		scanf("%d",&m),la=cnt;
		for(int i=1;i<=m;++i)++cnt,scanf("%lf%lf",&p[cnt].x,&p[cnt].y);
		for(int i=la+1;i<cnt;++i)e[i]=line(p[i],p[i+1]);
		e[cnt]=line(p[cnt],p[la+1]);
	}sort(e+1,e+cnt+1),q[++r]=1;
	for(int i=2;i<=cnt;++i){
		if(!sgn(e[i].art-e[i-1].art))continue;
		while(r-l>1&&(d[r]-e[i].s)*(e[i].t-e[i].s)>1e-8)--r;
		while(r-l>1&&(d[l+1]-e[i].s)*(e[i].t-e[i].s)>1e-8)++l;
		q[++r]=i;
		if(fabs((e[i].t-e[i].s)*(e[q[r-1]].t-e[q[r-1]].s))<1e-8){
			if((e[i].t-e[i].s)*(e[q[r-1]].t-e[i].s)>1e-8)return 0&printf("0.000");
		}
		if(r-l>1)d[r]=get(e[i],e[q[r-1]]);
	}while(r-l>1&&(d[r]-e[q[l+1]].s)*(e[q[l+1]].t-e[q[l+1]].s)>1e-8)--r;
	d[r+1]=get(e[q[l+1]],e[q[r]]),++r;
	for(int i=l+2;i<r;++i)ans+=d[i]*d[i+1];ans+=d[r]*d[l+2];
	return 0&printf("%.3lf",r-l>3?ans/2:0);
}
2024/4/26 21:44
加载中...