题目传送门 P4196 [CQOI2006]凸多边形 /【模板】半平面交

昨天没人回答/kel

就是运行了没有反应

包括在输入之前的也不输出

将调用 $\texttt{Halfplaneintersect}$ 的地方注释后则可运行

求查错/kel/kk

上面有很多函数没用 是自己模板里拷过来的

/*
***
还要继续努力
成为一名烤咕学家哦
***
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T> void rd(T &x){
	ll fl=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	x*=fl;
}
void wr(ll x){
	if(x<0) x=-x,putchar('-');
	if(x<10) putchar(x+'0');
	if(x>9) wr(x/10),putchar(x%10+'0');
}
const double pi=acos(-1.0),eps=1e-8;
ll sgn(double x){  //判断是否为0 
	if(fabs(x)<eps) return 0;
	return x<0.0?-1:1;
}
ll dcmp(double x,double y){   //比较浮点数大小 
	if(fabs(x-y)<eps) return 0;
	return x<y?-1:1;
}
struct Point{
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
	Point operator + (Point A){return Point(x+A.x,y+A.y);}
	Point operator - (Point A){return Point(x-A.x,y-A.y);}
	Point operator * (double k){return Point(x*k,y*k);}
	Point operator / (double k){return Point(x*k,y*k);}
	bool operator == (Point A){return sgn(x-A.x)==0&&sgn(y-A.y)==0;}
	bool operator < (Point A){return sgn(x-A.x)<0||sgn(x-A.x)==0&&sgn(y-A.y)<0;}  //用于凸包计算比较两点 
};
typedef Point Vector;
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}  //点积
double Len2(Vector A){return Dot(A,A);}
double Len(Vector A){return sqrt(Dot(A,A));}
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Len(A)/Len(B));}  //AB夹角
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}  //叉积
double Area(Point A,Point B,Point C){return Cross(B-A,C-A);}   //ABC三点形成三角形面积
double Dist(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}   //两点间距离
Vector Normal(Vector A){return Vector(-A.y/Len(A),-A.x/Len(A));}   //向量的法向量 
bool Parallel(Vector A,Vector B){return sgn(Cross(A,B))==0;}   //平行/重合
Vector Rotate(Vector A,double rad){return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}  //向量逆时针旋转rad度 
struct Line{
	Point p1,p2;
	double ang;
	Line(){}
	Line(Point p1,Point p2):p1(p1),p2(p2){}
	Line(Point p,double angle){
		p1=p;
		if(sgn(angle-pi/2)==0){p2=p1+Point(0,1);}
		else{p2=p1+Point(1,tan(angle));}
	} 
	Line(double a,double b,double c){
		if(sgn(a)==0){
			p1=Point(0,-c/b);
			p2=Point(1,-c/b);
		}
		else if(sgn(b)==0){
			p1=Point(-c/a,0);
			p2=Point(-c/a,1);
		}
		else{
			p1=Point(0,-c/b);
			p2=Point(1,(-c-a)/b);
		}
	}
	bool operator < (Line v){return ang<v.ang;}
};
typedef Line Segment;
double Line_angle(Line a){
	double k=atan2(a.p2.y-a.p1.y,a.p2.x-a.p1.x);
	if(sgn(k)<0) k+=pi;
	if(sgn(k-pi)==0) k-=pi;
	return k;
}   //直线倾角
ll Point_line_relation(Point p,Line v){
	ll c=sgn(Cross(p-v.p1,v.p2-v.p1));
	if(c<0) return 1;
	if(c>0) return 2;
	return 0;
}   //点和直线的关系 1 点在左边 2 点在右边 0 点在直线上
bool Point_on_seg(Point p,Line v){
	return sgn(Cross(p-v.p1,v.p2-v.p1))==0&&sgn(Dot(p-v.p1,p-v.p2))<=0;
}   //点和线段的关系 0 不在线段上 1 在线段上
ll Line_relation(Line v1,Line v2){
	if(sgn(Cross(v1.p2-v1.p1,v2.p2-v2.p1))==0){
		if(Point_line_relation(v1.p1,v2)==0) return 1;
		return 0;
	}
	return 2;
}   //两直线间的关系 0 平行 1 重合 2 相交
double Dis_point_line(Point p,Line v){return fabs(Cross(p-v.p1,v.p2-v.p1))/Dist(v.p1,v.p2);}   //点到直线的距离
Point Point_line_proj(Point p,Line v){
	double k=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
	return v.p1+(v.p2-v.p1)*k;
}   //点在直线上的投影
Point Point_line_symmetry(Point p,Line v){
	Point q=Point_line_proj(p,v);
	return Point(2*q.x-p.x,2*q.y-p.y);
}   //点关于直线的对称点
double Dis_point_seg(Point p,Segment v){
	if(sgn(Dot(p-v.p1,v.p2-v.p1))<0||sgn(Dot(p-v.p2,v.p1-v.p2))<0) return min(Dist(p,v.p1),Dist(p,v.p2));
	return Dis_point_line(p,v);
}   //点到线段的距离
Point Cross_point(Point a,Point b,Point c,Point d){
	double s1=Cross(b-a,c-a),s2=Cross(b-a,d-a);
	return Point(c.x*s2-d.x*s1,c.y*s2-d.y*s1)/(s2-s1);
}   //两直线ab和cd的交点 （调用前需保证两直线不平行或重合
bool Cross_segment(Point a,Point b,Point c,Point d){return sgn(Cross(b-a,c-a))*sgn(Cross(b-a,d-a))<0&&sgn(Cross(d-c,a-c))*sgn(Cross(d-c,b-c))<0;}   //两线段是否相交 1 相交 0 相离 （交点为端点不含 
//   ————————多边形qwq————————
const ll maxp=1e5+5;
struct Polygon{
	ll n;   //顶点数
	Point p[maxp];
	Line v[maxp]; 
};
ll Point_in_polygon(Point pt,Point *p,ll n){
	for(ll i=0;i<n;i++) if(p[i]==pt) return 3;
	for(ll i=0;i<n;i++) if(Point_on_seg(pt,Line(p[i],p[(i+1)%n]))) return 2;
	ll num=0;
	for(ll i=0;i<n;i++){
		ll j=(i+1)%n,c=sgn(Cross(pt-p[j],p[i]-p[j])),u=sgn(p[i].y-pt.y),v=sgn(p[j].y-pt.y);
		if(c>0&&u<0&&v>=0) num++;
		if(c<0&&u>=0&&v<0) num--;
	}
	return num!=0;
}   //判断点和任意多边形的关系 0 外部 1 内部 2 边上 3 点上
double Polygon_area(Point *p,ll n){
	double area=0;
	for(ll i=0;i<n;i++) area+=Cross(p[i],p[(i+1)%n]);
	return area/2;
}   //多边形面积 (面积正负不能直接取绝对值 
Point Polygon_center(Point *p,ll n){
	Point ans(0,0);
	if(Polygon_area(p,n)==0) return ans;
	for(ll i=0;i<n;i++) ans=ans+(p[i]+p[(i+1)%n])*Cross(p[i],p[(i+1)%n]);
	return ans/Polygon_area(p,n)/6;
}   //多边形重心
ll Convex_hull(Point *p,ll n,Point *ch){
	sort(p,p+n);
	n=unique(p,p+n)-p;
	ll v=0;
	for(ll i=0;i<n;i++){
		while(v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0) v--;
		ch[v++]=p[i];
	}
	ll j=v;
	for(ll i=n-2;i>=0;i--){
		while(v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0) v--;
		ch[v++]=p[i];
	}
	if(n>1) v--;
	return v;
}   //二维凸包 返回点个数 ch为点集 
double Rotating_calipers(Point *p,ll n,Point *a){
	//不要排序不要排序不要排序 
	double ans=0;
	for(ll i=0,j=1;i<n;i++){
		while(sgn(Cross(p[(i+1)%n]-p[i],p[j]-p[i])-Cross(p[(i+1)%n]-p[i],p[(j+1)%n]-p[i]))<0) j=(j+1)%n;
		if(dcmp(ans,Dist(p[j],p[i]))<0) ans=Dist(p[j],p[i]),a[0]=p[i],a[1]=p[j];
		if(dcmp(ans,Dist(p[j],p[(i+1)%n]))<0) ans=Dist(p[j],p[(i+1)%n]),a[0]=p[(i+1)%n],a[1]=p[j];
	}
	return ans;
}   //旋转卡壳
bool Onleft(Line v,Point p){return sgn(Cross(v.p2,p-v.p1))>0;}   //判断点在直线左边
Point Cross_P(Line a,Line b){
	Vector u=a.p1-b.p1;
	return a.p1+a.p2*Cross(b.p2,u)/Cross(a.p2,b.p2);
}   //半平面交用两直线交点 
Polygon Half_plane_intersect(Line *v,ll n){
	for(ll i=0;i<n;i++) v[i].ang=atan2(v[i].p2.y,v[i].p2.x);
	sort(v,v+n);
	Polygon ans;
	Line q[maxp];
	Point p[maxp];
	ll l=0,r=0;
	q[0]=v[0];
	for(ll i=1;i<n;i++){
		while(l<r&&!Onleft(v[i],p[r-1])) r--;
		while(l<r&&!Onleft(v[i],p[l])) l++;
		q[++l]=v[i];
		if(sgn(Cross(q[r].p2,q[l-1].p2))==0){
			r--;
			if(Onleft(q[r],v[i].p1)) q[r]=v[i];
		}
		if(l<r) p[r-1]=Cross_point(q[r-1].p1,q[r-1].p2+q[r-1].p1,q[r].p1,q[r].p2+q[r].p1);
	}
	while(l<r&&!Onleft(q[l],p[r-1])) r--;
	if(r-l<=1) return ans;
	p[r]=Cross_point(q[r].p1,q[r].p2+q[r].p1,q[l].p1,q[l].p2+q[l].p1);
	for(ll i=l;i<=r;i++) ans.p[i-l]=p[i];
	ans.n=r-l+1;
	return ans;
}
ll n,cnt;
Polygon a;
Point ans[maxp];
Line v[maxp];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cout<<"-----"<<endl;
	rd(n);
	for(ll i=0;i<n;i++){
		ll m=0;
		rd(m);
		for(ll j=0;j<m;j++) scanf("%lf %lf",&a.p[j].x,&a.p[j].y);
		for(ll j=0;j<m;j++) v[cnt+j].p1=a.p[j],v[cnt+j].p2=a.p[(j+1)%m]-a.p[j];
		cnt+=m;
	}
//	v[cnt].p1=Point(0,0),v[cnt].p2=Point(0,-1);
//	v[cnt+1].p1=Point(0,0x3f3f3f3f),v[cnt+1].p2=Point(-1,0);
//	cnt+=2;
//  已保证封闭 不需加极限
	Polygon an=Half_plane_intersect(v,cnt);
	double sum=Polygon_area(a.p,a.n);
	cout<<fixed<<setprecision(3)<<fabs(sum);puts(""); 
	return 0;
}