90分 WA#1
查看原帖
90分 WA#1
600333
2672434062xzl楼主2023/12/14 23:08
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<tuple>
using namespace std;
constexpr double eps=1e-7,pi=3.1415926535;
struct point {
	double x,y,angle;
	point() {
		x=0,y=0;
	}
	point(double a,double b) {
		x=a,y=b;
	}
	bool operator ==(const point p)const {
		return fabsl(x-p.x)<eps&&fabsl(y-p.y)<eps;
	}
};
typedef vector<point> polygon;
inline double length(point a,point b) {
	return sqrtl((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double Heron(point x,point y,point z) {
	if(x==y||z==y||x==z)return 0;
	double a=length(x,y),b=length(y,z),c=length(x,z);
	double p=(a+b+c)/2.0;
	return sqrtl(p*(p-a)*(p-b)*(p-c));
}
inline double area(point x,polygon q) {
	if(q.size()<3)return 0;
	double sum=0;
	for(size_t i=1; i<q.size(); ++i)
		sum+=Heron(x,q[i],q[i-1]);
	sum+=Heron(x,q[0],q[q.size()-1]);
	return sum;
}
 inline tuple<point,point,short> cross(point a,point b,point c,point d) {
//求AB与CD交点和是否有交点
	auto zero=make_tuple(point(),point(),0);
	if(fabsl((a.y-b.y)*(c.x-d.x)-(a.x-b.x)*(c.y-d.y))<eps&&fabsl(a.x-b.x)>eps&&fabsl(c.x-d.x)>eps) {//AB||CD或重合
		if(fabsl(a.x*(a.y-b.y)/(a.x-b.x)-c.x*(c.y-d.y)/(c.x-d.x)+c.y-a.y)>eps)return zero;
		if(fabsl(a.y-b.y)<eps) {
			if(a.x<b.x)swap(a,b);
			if(c.x<d.x)swap(c,d);
			if(b.x>c.x||a.x<d.x)return zero;
			if(a.x>=c.x&&d.x>=b.x)return make_tuple(c,d,2);
			if(c.x>=a.x&&b.x>=d.x)return make_tuple(a,b,2);
			if(c.x==b.x)return make_tuple(b,point(),1);
			if(a.x==d.x)return make_tuple(a,point(),1);
			if(c.x>b.x&&a.x>c.x)return make_tuple(c,b,2);
			if(a.x>d.x&&c.x>a.x)return make_tuple(a,d,2);
		}
		goto go;
	}
	if(fabsl(a.x-b.x)<eps&&fabsl(c.x-d.x)<eps) { //AB,CD垂直于X轴
		if(fabsl(a.x-c.x)>eps)return zero;
go:
		if(a.y<b.y)swap(a,b);
		if(c.y<d.y)swap(c,d);
		if(b.y>c.y||a.y<d.y)return zero;
		if(a.y>=c.y&&d.y>=b.y)return make_tuple(c,d,2);
		if(c.y>=a.y&&b.y>=d.y)return make_tuple(a,b,2);
		if(c.y==b.y)return make_tuple(b,point(),1);
		if(a.y==d.y)return make_tuple(a,point(),1);
		if(c.y>b.y&&a.y>c.y)return make_tuple(c,b,2);
		if(a.y>d.y&&c.y>a.y)return make_tuple(a,d,2);
	}
	if(fabsl(a.x-b.x)<eps)goto go1;//AB垂直于X轴
	if(fabsl(c.x-d.x)<eps) {//CD垂直于X轴
		swap(a,c);
		swap(b,d);
go1:
		point tmp(a.x,(c.y-d.y)/(c.x-d.x)*(a.x-c.x)+c.y);
		if(fabsl(length(tmp,a)+length(tmp,b)-length(a,b))>eps
		        ||fabsl(length(tmp,c)+length(tmp,d)-length(c,d))>eps)return zero;
		return make_tuple(tmp,point(),1);
	}
	double tmpy,tmpx=(a.x*(a.y-b.y)/(a.x-b.x)-c.x*(c.y-d.y)/(c.x-d.x)+c.y-a.y)
	                 /((a.y-b.y)/(a.x-b.x)-(c.y-d.y)/(c.x-d.x));
	tmpy=(a.y-b.y)/(a.x-b.x)*(tmpx-a.x)+a.y;
	point tmp(tmpx,tmpy);
	if(fabsl(length(tmp,a)+length(tmp,b)-length(a,b))>eps
	        ||fabsl(length(tmp,c)+length(tmp,d)-length(c,d))>eps)return zero;
	return make_tuple(tmp,point(),1);
}
inline void unique(polygon &q){
	if(q.empty())return;
	polygon p;
	p.push_back(q.front());
	for(size_t i=1;i<q.size();++i){
		if(q[i]==p.back())continue;
		p.push_back(q[i]);
	}
	q=p;
	return;
}
inline void sort(polygon &q) {
	if(q.empty())return;
	point middle=point((q.front().x+q.back().x)/2.0,(q.front().y+q.back().y)/2.0);//计算内点
	for(auto &i:q) {
		i.x-=middle.x;
		i.y-=middle.y;
		if(fabsl(i.x)<eps) {
			i.angle=(i.y>0?pi/2.0:pi*1.5);
			continue;
		}
		if(i.x>0&&i.y>=0)i.angle=atan(i.y/i.x);
		else if(i.x>0&&i.y<0)i.angle=2.0*pi+atan(i.y/i.x);
		else i.angle=pi+atan(i.y/i.x);
	}//计算与内点角度,
	sort(q.begin(),q.end(),
	[](const point& a,const point& b) {
		return a.angle<=b.angle;
	});//按角度排序
	for(auto &i:q) {
		i.x+=middle.x;
		i.y+=middle.y;
	}
	unique(q);
	return;
}
polygon work(polygon q1,polygon q2){
	polygon q;
	if(q1.empty()||q2.empty())return q;
	double s1,s2;
	s1=area(q1.back(),q1);
	s2=area(q2.back(),q2);
	for(auto i:q1)
		if(fabsl(area(i,q2)-s2)<eps)q.push_back(i);
	for(auto i:q2)
		if(fabsl(area(i,q1)-s1)<eps)q.push_back(i);
 	int n=q1.size(),m=q2.size();
	for(int i=0; i<n; ++i)
		for(int j=0; j<m; ++j) {
			auto tmp=cross(q1[i],q1[(i+1)%n],q2[j],q2[(j+1)%m]);
			if(get<2>(tmp)) {
				q.push_back(get<0>(tmp));
				if(get<2>(tmp)==2)q.push_back(get<1>(tmp));
			}
		}
	sort(q);
	return q;
}
polygon q[20];
int main() {
	int n,m;
	double x,y;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>m;
		for(int j=1; j<=m; ++j) {
			scanf("%lf%lf",&x,&y);
			q[i].push_back(point(x,y));
		}
		if(i>1)q[i]=work(q[i],q[i-1]);
	}
	if(q[n].empty())cout<<"0.000";
	else printf("%.3lf",area(q[n].back(),q[n]));
	return 0;
}
2023/12/14 23:08
加载中...