【BZOJ2618】[CQOI2006]凸多边形（半平面交）

题面

BZOJ

洛谷

题解

这个东西就是要求凸多边形的边所形成的半平面交。

那么就是一个半平面交模板题了。

这里写的是平方的做法。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAX 10010

#define inf 1000

#define double long double

const double eps=0;

struct Point{double x,y,ang;};

bool operator<(Point a,Point b){return (a.ang!=b.ang)?a.ang<b.ang:a.x<b.x;}

Point operator+(Point a,Point b){return (Point){a.x+b.x,a.y+b.y};}

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

Point operator*(Point a,double b){return (Point){a.x*b,a.y*b};}

Point operator/(Point a,double b){return (Point){a.x/b,a.y/b};}

double operator*(Point a,Point b){return a.x*b.x+a.y*b.y;}

double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}

double Len(Point a){return sqrt(a.x*a.x+a.y*a.y);}

double Dis(Point a,Point b){return Len(a-b);}

Point Rotate(Point p,double a){double c=cos(a),s=sin(a);return (Point){p.x*c-p.y*s,p.x*s+p.y*c};}

struct Line{Point a,v;};

Point S[MAX],tmp[MAX];int top;

Point Intersection(Line a,Line b)

{

	Point c=b.a-a.a;

	double t=Cross(b.v,c)/Cross(b.v,a.v);

	return a.a+a.v*t;

}

void pre()

{

	top=0;

	S[++top]=(Point){inf,inf};

	S[++top]=(Point){-inf,inf};

	S[++top]=(Point){-inf,-inf};

	S[++top]=(Point){inf,-inf};

}

void Cut(Line a)

{

	S[top+1]=S[1];int tot=0;

	for(int i=1;i<=top;++i)

	{

		double v1=Cross(a.v,S[i]-a.a);

		double v2=Cross(a.v,S[i+1]-a.a);

		if(v1>=0)tmp[++tot]=S[i];

		if(v1*v2<0)tmp[++tot]=Intersection(a,(Line){S[i],S[i+1]-S[i]});

	}

	top=tot;for(int i=1;i<=top;++i)S[i]=tmp[i];

}

int n;Point p[MAX];

int main()

{

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

	while(T--)

	{

		scanf("%d",&n);

		for(int i=1;i<=n;++i)scanf("%Lf%Lf",&p[i].x,&p[i].y);

		for(int i=1;i<=n;++i)p[i].x+=eps;

		p[n+1]=p[1];

		for(int i=1;i<=n;++i)Cut((Line){p[i],p[i+1]-p[i]});

		continue;

	}

	double ans=0;S[top+1]=S[1];

	for(int i=2;i<=top;++i)ans+=Cross(S[i]-S[1],S[i+1]-S[1]);

	printf("%.3Lf\n",ans/2);

}