●BZOJ 2618 [Cqoi2006]凸多边形

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=2618

题解：

计算几何，半平面交。

给出一些凸包，求面积交。

把所有边都取出来，直接办平面交就好。
    
原来dcmp也不能滥用，之前把所有的大于小于比较都用了dcmp函数，导致错误。

（以后除了double型判等，其它时候尽量不用dcmp好了）

代码：

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 1550

using namespace std;

const double eps=1e-8;

int dcmp(double x){

	if(fabs(x)<=eps) return 0;

	return x<0?-1:1;

}

struct Point{

	double x,y;

	Point(double _x=0,double _y=0):x(_x),y(_y){}

	void Read(){scanf("%lf%lf",&x,&y);}

}D[MAXN];

typedef Point Vector;

struct Line{

	Point s; Vector v; double ang;

	Line(){}

	Line(Point _s,Vector _v):s(_s),v(_v){ang=atan2(v.y,v.x);}

	friend bool operator < (Line A,Line B){return A.ang<B.ang;}

}L[MAXN];

bool operator == (Point A,Point B){return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0;}

Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}

Vector operator * (Vector A,double k){return Vector(A.x*k,A.y*k);}

double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}

bool OnRight(Point P,Line A){return (A.v^(P-A.s))<0;}

Point LLI(Line A,Line B){//Line_Line_Intersection

	Vector u=B.s-A.s;

	double t=(u^B.v)/(A.v^B.v);

	return A.s+A.v*t;

}

int HPI(int n){

	static Point QP[MAXN]; static Line QL[MAXN];

	sort(L+1,L+n+1);

	int l=1,r=1,dnt=0; QL[1]=L[1];

	for(int i=2;i<=n;i++){

		while(l<r&&OnRight(QP[r-1],L[i])) r--;

		while(l<r&&OnRight(QP[l],L[i])) l++;

		QL[++r]=L[i];

		if(QL[r].v*QL[r-1].v>0&&dcmp(QL[r].v^QL[r-1].v)==0){

			r--; if(OnRight(QL[r].s,L[i])) QL[r]=L[i];

		}

		if(l<r) QP[r-1]=LLI(QL[r-1],QL[r]);

	}

	while(l<r&&OnRight(QP[r-1],QL[l])) r--;

	if(r-l<=1) return 0;

	QP[r]=LLI(QL[l],QL[r]);

	for(int i=l;i<=r;i++) D[++dnt]=QP[i];

	dnt=unique(D+1,D+dnt+1)-D-1;

	return dnt-(dnt>1&&D[1]==D[dnt]);

}

double PArea(int n){//Polygon_Area

	double S=0; D[n+1]=D[1];

	for(int i=1;i<=n;i++) S+=D[i]^D[i+1];

	return fabs(S)/2;

}

int main(){

	int n,m,dnt=0,p; scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d",&m);p=dnt;

		for(int j=1;j<=m;j++){

			D[++dnt].Read();

			if(j>1) L[dnt-1]=Line(D[dnt-1],D[dnt]-D[dnt-1]);

		}

		L[dnt]=Line(D[dnt],D[p+1]-D[dnt]);

	}

	dnt=HPI(dnt);

	printf("%.3lf\n",PArea(dnt));

	return 0;

}