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

2018-11-29 17:11:34


半平面交模板题

可以建议改成【模板】半平面交

半平面交是什么

感觉前面大家讲得都复杂了,让读者误以为半平面交是一个很难实现的算法

据我所了解的来看,就是求若干半平面的交,本题体现在多边形的每条边分割的两个半平面的交平面

怎么实现

共分三个部分:

  • 计算两个直线的交点(Add函数,用定比分点实现)
  • 计算面积(CalcS函数,用叉积的几何意义实现)
  • 求已有平面与新的一个半平面的交(Cut,画画图可以知道)

如果理解起来有问题可以再看看我的博客

如果实现起来有问题可以参照代码

#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;
}