P4196 [CQOI2006]凸多边形

半平面交的讲解

然而这个代码真的是非常的迷……并不怎么看得懂……
//minamoto

#include<bits/stdc++.h>

#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)

#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)

using namespace std;

const int N=1e5+5;const double eps=1e-9;

inline int dcmp(const double &a){return fabs(a)>=eps?a<0?-1:1:0;}

struct node{double x,y;}pt[N];int tot;

inline node operator -(node a,node b){return {a.x-b.x,a.y-b.y};}

inline double operator *(node a,node b){return a.x*b.y-a.y*b.x;}

struct line{node a,b;}p[N],dq[N];int tp,bt,n;

inline bool aboveX(line a){

	if(!dcmp(a.b.y-a.a.y))return dcmp(a.b.x-a.a.x)>0;

	return dcmp(a.b.y-a.a.y)>0;

}

inline bool cmp(line a,line b){

	if(aboveX(a)!=aboveX(b))return aboveX(a);

	if(!dcmp((a.b-a.a)*(b.b-b.a)))return dcmp((a.b-a.a)*(b.b-a.a))<0;

	return dcmp((a.b-a.a)*(b.b-b.a))>0;

}

inline node get(line a,line b){

	double a1=a.b.y-a.a.y,b1=a.a.x-a.b.x,c1=a.a*a.b;

	double a2=b.b.y-b.a.y,b2=b.a.x-b.b.x,c2=b.a*b.b;

	double d=a1*b2-a2*b1;

	return {(b2*c1-b1*c2)/d,(a1*c2-a2*c1)/d};

}

inline bool pd(line a,line b,line c){

	node p=get(a,b);

	return dcmp((p-c.a)*(c.b-c.a))>-1;

}

void solve(){

	tot=1;

	fp(i,1,n)if(dcmp((p[i].b-p[i].a)*(p[tot].b-p[tot].a)))p[++tot]=p[i];

	n=tot,dq[bt=1]=p[1],dq[tp=2]=p[2];

	fp(i,3,n){

		while(tp>bt&&pd(dq[tp],dq[tp-1],p[i]))--tp;

		while(tp>bt&&pd(dq[bt],dq[bt+1],p[i]))++bt;

		dq[++tp]=p[i];

	}

	while(tp>bt&&pd(dq[tp],dq[tp-1],dq[bt]))--tp;

	while(tp>bt&&pd(dq[bt],dq[bt+1],dq[tp]))++bt;

	dq[++tp]=dq[bt],tot=0;

	fp(i,bt,tp-1)pt[++tot]=get(dq[i],dq[i+1]);

}

double area(double s=0){

	if(tot<3)return 0;pt[++tot]=pt[1];

	fp(i,1,tot-1)s+=pt[i]*pt[i+1];

	return 0.5*fabs(s);

}

int main(){

//	freopen("testdata.in","r",stdin);

	int T;scanf("%d",&T);

	while(T--){

		int ps;scanf("%d",&ps);

		fp(i,1,ps)scanf("%lf%lf",&pt[i].x,&pt[i].y);

		pt[0]=pt[ps];

		fp(i,0,ps-1)p[++n].a=pt[i],p[n].b=pt[i+1];

	}

	sort(p+1,p+1+n,cmp);

	solve();double ans=area();printf("%.3lf\n",ans);return 0;

}
巴特西

P4196 [CQOI2006]凸多边形

最新文章

热门文章
