凸多边形半平面交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

//逆时针给出 n 个凸多边形的顶点坐标，求它们交的面积

#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);//π
const double eps = 1e-8;
int sign(double x) { // 符号函数
    if (fabs(x) < eps) return 0;//x是0
    if (x < 0) return -1;//x是负数
    return 1;//x是正数
}
struct Point{
    double x, y;
   Point(double x = 0, double y = 0) : x(x), y(y) { }
    Point operator +(Point B){return Point(x+B.x,y+B.y);}
    Point operator -(Point B){return Point(x-B.x,y-B.y);}
    Point operator *(double k){return Point(x*k,y*k);}
    Point operator /(double k){return Point(x/k,y/k);}
    bool operator == (Point B){return sign(x-B.x)==0&&sign(y-B.x)==0;}
    bool operator <(Point B)//排序
{return sign(x-B.x)<0||sign(x-B.x)==0&&sign(y-B.y)<0;}

};
typedef Point Vector;
typedef Point PT;
double cross(Point a, Point b){//外积（叉积）
//向量A与B张成的平行四边形的有向面积。B在A的逆时针方向为正。
//如果等0则，两个向量平行
     return a.x * b.y - b.x * a.y;
}
double area(Point a, Point b, Point c){
//计算向量ab与ac构成的平行四边形有向面积
     return cross(a - b, a - c);
}
int to_cmp(double x, double y){  // 比较函数
    if (fabs(x - y) < eps) return 0;//相等
    if (x < y) return -1;
    return 1;
}
double get_angle(Point a, Point b){ 
//计算向量A->B角
// return acos(dot(a, b) / get_length(a) / get_length(b));
//计算AB向量的极角
 return atan2(a.y - b.y, a.x - b.x);
}
Point get_line_intersection(Point p, Vector v, Point q, Vector w)
{//两直线的交点
// 使用前提，直线必须有交点
// cross(v, w) == 0则两直线平行或者重合
Vector u = p - q;
double t = cross(w, u) / cross(v, w);
    return p + v * t;
} 
const int N=1e5+10;
int n,m;
int cnt,q[N];
Point pg[N],res[N];
struct Line//向量
{
   Point st, ed; //记录当前直线的起点坐标和终点坐标
  bool operator<(Line TB){
//按照直线的角度从小到大排序
////如果两条直线角度相同，则将靠左的排在前面
     double A = get_angle(st,ed), B = get_angle(TB.st,TB.ed);
    if(!to_cmp(A, B)) return area(st, ed, TB.ed) < 0; //如果两条直线角度相同，则将靠左的排在前面
    return A < B;
  }

}line[N]; //存储所有直线
//俩直线交点
Point get_line_intersection(Line a,Line b){
     return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}
bool on_right(Line a, Line b, Line c) //判断 b 和 c 的交点是否在 a 的右侧
{
    Point o = get_line_intersection(b, c); //求 b 和 c 的交点
    return sign(area(a.st, a.ed, o)) <= 0;
}
double get_angle(Line a) {
    return get_angle(a.st,a.ed);
}
double half_plane_intersection() //求半平面交
{
    sort(line, line + cnt); //将所有直线按照角度从小到大排序
    int hh = 0, tt = -1;
    for(int i = 0; i < cnt; i++)
    {
        if(i && !to_cmp(get_angle(line[i]), get_angle(line[i - 1]))) continue; //角度相同的直线只考虑最靠左的一条
        while(hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]])) tt--; //删除队尾无用直线
        while(hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh++; //删除队头无用直线
        q[++tt] = i; //将当前直线加入队列
    }
    while(hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt--; //用队头更换队尾
    while(hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh++; //用队尾更新队头

    q[++tt] = q[hh]; //将队头重复加入队尾
    int k = 0;
    //求出半平面交上的所有顶点
    for(int i = hh; i < tt; i++) res[k++] = get_line_intersection(line[q[i]], line[q[i + 1]]);

    double ans = 0; //记录半平面交的面积
    for(int i = 1; i + 1 < k; i++) ans += area(res[0], res[i], res[i + 1]); //求半平面交（凸多边形）的面积
    return ans / 2;
}
void solve(){
    cin>>n;
    while(n--){
        cin>>m;
         for(int i = 0; i < m; i++)
            cin>>pg[i].x>>pg[i].y;
        for(int i = 0; i < m; i++)//多边形形成的向量
        line[cnt++] = {pg[i], pg[(i + 1) % m]};
    }
    double res= half_plane_intersection(); //求半平面交
    cout<<fixed<<setprecision(3)<<res;
}
signed main(){
     solve();
}