【模板】【poj1279】 计几半平面交求多边形内核 nlogn

题目链接：https://vjudge.net/problem/POJ-1279

参考：https://blog.csdn.net/commonc/article/details/55260747

以及：https://blog.csdn.net/commonc/article/details/55252420

题意：求多边形内核的面积。

都在注释里了。nlogn半平面交模板

  1 /*************************************************************************
  2     > File Name: poj1279.cpp
  3 # File Name: poj1279.cpp
  4 # Author : xiaobuxie
  5 # QQ : 760427180
  6 # Email:[email protected]
  7 # Created Time: 2019年09月26日 星期四 16时12分12秒
  8  ************************************************************************/
  9 
 10 #include<iostream>
 11 #include<cstdio>
 12 #include<map>
 13 #include<cmath>
 14 #include<cstring>
 15 #include<set>
 16 #include<queue>
 17 #include<vector>
 18 #include<algorithm>
 19 using namespace std;
 20 typedef long long ll;
 21 #define inf 0x3f3f3f3f
 22 #define pq priority_queue<int,vector<int>,greater<int> >
 23 ll gcd(ll a,ll b){
 24     if(a<b) return gcd(b,a);
 25     return b==0?a:gcd(b,a%b);
 26 }
 27 const int N = 1500+9;
 28 #define eps 1e-8
 29 
 30 
 31 
 32 //q和L代表原来点和原来向量
 33 //quel代表队列里的向量,queq[i]代表quel[i] 和 quel[i+1]的交点
 34 int n,h,t;
 35 struct Point{
 36     double x,y;
 37     Point operator - (const Point & b)const{
 38         return (Point){x-b.x,y-b.y};
 39     }
 40     Point operator + (const Point& b)const{
 41         return (Point){x+b.x , y+b.y};
 42     }
 43     Point operator * (double b)const{
 44         return (Point){x*b,y*b};
 45     }
 46     double operator ^ (const Point& b)const{
 47         return x*b.y-b.x*y;
 48     }
 49 }p[N],quep[N];
 50 // Line是有向向量，ang代表和x轴的角度，选的半平面在向量的右面，即交点在向量左边的舍去
 51 struct Line{
 52     Point s,t;
 53     double ang;
 54     //注意ang相同时
 55     bool operator < (const Line& b)const{
 56         if(ang != b.ang) return ang < b.ang;
 57         return ( (b.t - s) ^ (b.s - s) ) >0;
 58     }
 59 }L[N],quel[N];
 60 
 61 int sgn(double x){
 62     if(fabs(x) < eps) return 0;
 63     if(x > 0) return 1;
 64     return -1;
 65 }
 66 // clock wise判断是否为顺时针，要把点弄成顺时针(这里处理点是顺或逆的),如果乱序，直接极角排序
 67 bool cw(){
 68     double res=0;
 69     for(int i=2; i<n ; ++i){
 70         res += ( (p[i]-p[1]) ^ (p[i+1]-p[1]) );
 71     }
 72     return sgn(res) < 0;
 73 }
 74 //判断点是否在向量左边
 75 bool onleft(Point u, Line a){
 76     return sgn( (a.s-u) ^ (a.t-u) ) > 0; 
 77 }
 78 //两直线交点
 79 Point line_inter(Line l1,Line l2){
 80     double b = ((l1.t-l1.s)^(l2.s-l1.s))/((l2.t-l2.s)^(l1.t-l1.s));
 81     return l2.s + (l2.t - l2.s)*b;
 82 }
 83 void init(){
 84     scanf("%d",&n);
 85     for(int i=1;i<=n;++i) scanf("%lf %lf",&p[i].x,&p[i].y);
 86     if( !cw() ) reverse(p+1,p+1+n);
 87     p[n+1]=p[1];
 88     for(int i=1;i<=n;++i) L[i]=(Line){ p[i], p[i+1], atan2(p[i+1].y-p[i].y,p[i+1].x-p[i].x)};
 89     sort(L+1,L+1+n);
 90     int nn=1;
 91     for(int i=2;i<=n;++i){
 92         if(L[i].ang != L[i-1].ang) L[++nn]=L[i];
 93     }
 94     n = nn;
 95 }
 96 //处理半平面交
 97 void solve(){
 98     h = t = 1;
 99     quel[1] = L[1];
100     for(int i = 2 ; i<=n ; ++i ){
101         while( h<t && onleft( quep[t-1] , L[i] ) ) --t;
102         while( h<t && onleft( quep[h], L[i]) ) ++h;
103         quel[++t] = L[i];
104         if( h<t ) quep[t-1] = line_inter(quel[t-1],quel[t]);
105     }
106     while( h<t && onleft( quep[t-1] , quel[h] ) ) --t;
107     quep[t] = line_inter(quel[h],quel[t]);
108 }
109 //求多边形内核的面积
110 void solve_area(){
111     double area=0;
112     for(int i=h+1; i<t ; ++i){
113         area += ( (quep[i] - quep[h]) ^ (quep[i+1] - quep[h]) );
114     }
115     area/=2;
116     printf("%.2f\n",area);
117 }
118 int main(){
119     int T; scanf("%d",&T);
120     while(T--){
121         init();
122         solve();
123         solve_area();
124     }
125     return 0;
126 }