题解 P4196 【[CQOI2006]凸多边形】

xzyxzy

2018-11-29 17:11:34

Solution

# 半平面交模板题 可以建议改成【模板】半平面交 ### 半平面交是什么 感觉前面大家讲得都复杂了,让读者误以为半平面交是一个很难实现的算法 据我所了解的来看,就是求若干半平面的交,本题体现在多边形的每条边分割的两个半平面的交平面 ### 怎么实现 共分三个部分: - 计算两个直线的交点(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; } ```