题解 P4196 【[CQOI2006]凸多边形】
xzyxzy
2018-11-29 17:11:34
# 半平面交模板题
可以建议改成【模板】半平面交
### 半平面交是什么
感觉前面大家讲得都复杂了,让读者误以为半平面交是一个很难实现的算法
据我所了解的来看,就是求若干半平面的交,本题体现在多边形的每条边分割的两个半平面的交平面
### 怎么实现
共分三个部分:
- 计算两个直线的交点(Add函数,用定比分点实现)
- 计算面积(CalcS函数,用叉积的几何意义实现)
- 求已有平面与新的一个半平面的交(Cut,画画图可以知道)
如果理解起来有问题可以再看看[我的博客](https://www.cnblogs.com/xzyxzy/p/10033130.html)
如果实现起来有问题可以参照代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=510;
struct Node
{
double x,y;
Node operator - (const Node A) {return (Node){x-A.x,y-A.y};}
Node operator + (const Node A) {return (Node){x+A.x,y+A.y};}
Node operator * (double t) {return (Node){x*t,y*t};}
double crs(Node A) {return x*A.y-y*A.x;}
}A[N],B[N],C[N];
int n,m,tt,node;
void Add(Node a1,Node a2,Node b1,Node b2)
{
Node a=a2-a1,b=b2-b1,c=b1-a1;
double t=b.crs(c)/b.crs(a);
C[++tt]=a1+a*t;
}
void Cut(Node a,Node b)
{
tt=0;A[node+1]=A[1];
for(int i=1;i<=node;i++)
if((a-A[i]).crs(b-A[i])>=0)
{
C[++tt]=A[i];
if((a-A[i+1]).crs(b-A[i+1])<0)
Add(A[i],A[i+1],a,b);
}
else if((a-A[i+1]).crs(b-A[i+1])>=0)
Add(A[i],A[i+1],a,b);
for(int i=1;i<=tt;i++) A[i]=C[i];
node=tt;
}
double CalcS()
{
double res=0;
for(int i=2;i<node;i++) res+=(A[i]-A[1]).crs(A[i+1]-A[1]);
return res/2;
}
int main()
{
cin>>n>>m;node=m;n--;
for(int i=1;i<=m;i++) cin>>A[i].x>>A[i].y;
while(n--)
{
cin>>m>>B[1].x>>B[1].y;B[m+1]=B[1];
for(int i=2;i<=m;i++) cin>>B[i].x>>B[i].y;
for(int i=1;i<=m;i++) Cut(B[i],B[i+1]);
}
return printf("%.3f\n",CalcS()),0;
}
```