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

很明显是一道半平面交的题。

先说一下半平面交的步骤：

1.用点向法（点+向量）表示直线

2.极角排序，若极角相同，按相对位置排序。

3.去重，极角相同的保留更优的

4.枚举边维护双端队列

5.求答案

1就不说了，2中的极角可以用atan2(y,x)来求,因为atan2精度要高

双端队列的原因是新加的一条边对头和尾都有影响,如图：

如何去判断：只要判断线head和线head+1,的交点p与新的一条线的位置关系就可以

至于交点的求法：先见图：

求\(p_1v_1,p_2v_2\)的交点\(p_0\)

设\(p_0=p_2+kv_2\ \ u=p_2-p_1\)

\(S_1=u\times v_1,S_2=v_1\times v_2,k=S_1/S2\)

所以\(p_0=p_2+kv_2\)

\(S_1\)为\(u\)与\(v_1\)的面积，\(S_2\)为\(v_1\)与\(v_2\)的面积，按比例求得\(k\)再乘一下就求出\(p_0\)

最后统计答案

细节见代码：

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<bitset>

#include<vector>

#include<cstdlib>

#define QAQ int

#define TAT long long

#define OwO bool

#define ORZ double

#define F(i,j,n) for(QAQ i=j;i<=n;++i)

#define E(i,j,n) for(QAQ i=j;i>=n;--i)

#define MES(i,j) memset(i,j,sizeof(i))

#define MEC(i,j) memcpy(i,j,sizeof(j))

using namespace std;

const int N=505;

const double eps=1e-8;

int n;

struct Point{

	double x,y;

	friend Point operator - (Point a,Point b){

		Point t;

		t.x=a.x-b.x;t.y=a.y-b.y;

		return t;

	}

	friend Point operator + (Point a,Point b){

		Point t;

		t.x=a.x+b.x;t.y=a.y+b.y;

		return t;

	}

	friend double operator * (Point a,Point b){

		return a.x*b.x+a.y*b.y;

	}

	friend double operator ^ (Point a,Point b){

		return a.x*b.y-b.x*a.y;

	}

	friend Point operator * (double k,Point b){

		Point t;

		t.x=k*b.x;t.y=k*b.y;

		return t;

	}

}b[N];

int sign(double x){

	return fabs(x)<=eps ?  0 : (x>0 ? 1 : -1);

}

struct Line{

	Point p,v;

	double poa;

	friend OwO operator < (Line x,Line y){

		return sign(x.poa-y.poa)==0 ? sign((x.v-x.p) ^ (y.v-x.p)) >0 : sign(x.poa-y.poa)<0;

		//因为我是向量左侧求交，所以极角相同时靠左的更优，把优的放在后面，方便之后的操作 ，可以画图体会一下

	}

}a[N],q[N];

int js,cnt,head,tail;

double ans;

Point inter(Line a,Line b){//求交点

	Point p1=a.p,p2=b.p,v1=a.v,v2=b.v;

	v1=v1-p1;v2=v2-p2;

	Point u=p2-p1;

	Point p=p2+((u^v1)/(v1^v2))*v2;

	return p;

}

OwO pd(Line i,Line j,Line k){

	Point p=inter(i,j);

	return sign((k.v-k.p) ^ (p-k.p))<0;

}

void Half_Plane(){

	sort(a+1,a+js+1);//排序

	F(i,1,js) {

		if(sign(a[i].poa-a[i-1].poa)!=0) cnt++;

		a[cnt]=a[i];//因为排过序，即使极角相同，后面的也比前面的优

	}

	head=1;tail=0;

	q[++tail]=a[1];q[++tail]=a[2];

	F(i,3,cnt){

		while(head<tail&&pd(q[tail-1],q[tail],a[i])) tail--;//维护双端队列

		while(head<tail&&pd(q[head+1],q[head],a[i])) head++;

		q[++tail]=a[i];

	}

	while(head<tail&&pd(q[tail-1],q[tail],q[head])) tail--;

	while(head<tail&&pd(q[head+1],q[head],q[tail])) head++;

	q[tail+1]=q[head];

	js=0;

	F(i,head,tail) b[++js]=inter(q[i],q[i+1]);

}

int main(){

	scanf("%d",&n);

	F(i,1,n){

		int k;

		scanf("%d",&k);

		F(j,1,k) scanf("%lf%lf",&b[j].x,&b[j].y);

		b[k+1]=b[1];

		F(j,1,k) a[++js].p=b[j],a[js].v=b[j+1];

	}

	F(i,1,js) a[i].poa=atan2(a[i].v.y-a[i].p.y,a[i].v.x-a[i].p.x);

	Half_Plane();

	b[js+1]=b[1];

	if(js>2) F(i,1,js) ans+=(b[i]^b[i+1]);

	ans=fabs(ans)/2.0;

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

	return 0;

}

巴特西

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

最新文章

热门文章