卧薪尝胆,厚积薄发。
CQOI2006 凸多边形
Date: Tue Aug 14 15:26:13 CST 2018 In Category: NoCategory

Description:

逆时针给出 $n$ 个凸多边形的顶点坐标,求它们交的面积。
$2\le n \le 10$

Solution:

把多边形拆成很多边,作半平面交。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int tot;
#define eps 1e-10
int n;
#define MAXN 1000
struct point
{
double x,y;
point(double x_ = 0.0,double y_ = 0.0){x = x_;y = y_;}
}p[MAXN];
typedef point vector;
vector operator + (vector a,vector b){return vector(a.x + b.x,a.y + b.y);}
vector operator - (vector a,vector b){return vector(a.x - b.x,a.y - b.y);}
vector operator * (vector a,double b){return vector(a.x * b,a.y * b);}
double dotmul(vector a,vector b){return a.x * b.x + a.y * b.y;}
double crossmul(vector a,vector b){return a.x * b.y - a.y * b.x;}
double angle(vector a){return atan2(a.y,a.x);}
bool equal(double x,double y){return fabs(x - y) < eps;}
int sign(double x){return (equal(x,0.0) ? 0 : (x < 0 ? -1 : 1));}
struct plane
{
point p;vector v;
plane(){};
plane(point p_,vector v_){p = p_;v = v_;}
}pl[MAXN],q[MAXN];
int head,tail;
bool in(point p,plane k){return sign(crossmul(p - k.p,k.v)) >= 0;}
point intersection(plane a,plane b){return b.p + b.v * (crossmul(a.v,a.p - b.p) / crossmul(a.v,b.v));}
bool cmp(plane a,plane b){return angle(a.v) < angle(b.v);}
#define F 1000
#define N -1000
double HPI()
{
pl[++n] = plane(point(N,N),vector(0,1));
pl[++n] = plane(point(N,F),vector(1,0));
pl[++n] = plane(point(F,F),vector(0,-1));
pl[++n] = plane(point(F,N),vector(-1,0));
sort(pl + 1,pl + 1 + n,cmp);
int n0 = 0;
for(int i = 1;i <= n;++i)
{
if(n0 == 0)pl[++n0] = pl[i];
else if(!equal(angle(pl[n0].v),angle(pl[i].v)))pl[++n0] = pl[i];
else if(in(pl[i].p,pl[n0]))pl[n0] = pl[i];
}
n = n0;head = 1;tail = 2;
q[1] = pl[1];q[2] = pl[2];
for(int i = 3;i <= n;++i)
{
while(head < tail && !in(intersection(q[tail],q[tail - 1]),pl[i]))--tail;
while(head < tail && !in(intersection(q[head],q[head + 1]),pl[i]))++head;
if(head == tail && sign(crossmul(q[head].v,pl[i].v)) <= 0)return 0;
q[++tail] = pl[i];
}
while(head < tail && !in(intersection(q[tail],q[tail - 1]),q[head]))--tail;
int m = tail - head + 1;
for(int i = 1;i < m;++i)p[i] = intersection(q[head + i],q[head + i - 1]);
p[0] = p[m] = intersection(q[head],q[tail]);
double res = 0.0;
for(int i = 0;i < m;++i)res += crossmul(p[i],p[i + 1]);
return res * 0.5;
}
point ps[51];
int main()
{
scanf("%d",&tot);
n = 0;
int k;
for(int i = 1;i <= tot;++i)
{
scanf("%d",&k);
for(int j = 1;j <= k;++j)
{
cin >> ps[j].x >> ps[j].y;
}
for(int j = 2;j <= k;++j)
{
pl[++n] = plane(ps[j],ps[j - 1] - ps[j]);
}
pl[++n] = plane(ps[1],ps[k] - ps[1]);
}
printf("%.3lf\n",HPI());
return 0;
}
In tag:
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡