Plane semi intersecting plate

Test P4196 [CQOI2006] Convex polygon /【 Templates 】 Half plane intersection

#include<bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;
#define x first
#define y second
const double eps = 1e-8;
struct Line{
    
    pdd st,ed;
};
int sgn(double x){
    
    if(fabs(x) < eps) return 0;
    if(x > 0) return 1;
    return -1;
}
int dcmp(double a,double b){
    
    if(fabs(a-b) < eps) return 0;
    if(a > b) return 1;
    return -1;
}
pdd operator - (pdd a,pdd b){
    return {
    a.x-b.x,a.y-b.y};}
pdd operator + (pdd a,pdd b){
    return {
    a.x+b.x,a.y+b.y};}
pdd operator * (pdd a,double p) {
    return {
    a.x*p,a.y*p};}
double Cross(pdd a,pdd b){
    return a.x*b.y-a.y*b.x;}
double area(pdd a,pdd b,pdd c){
    
    return Cross(b-a,c-a);
}
double GetA(Line a)
{
    
    return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}
bool cmp( Line a, Line b)
{
    
    double A = GetA(a), B = GetA(b);
    if (!dcmp(A, B)) return sgn(area(a.st, a.ed, b.ed)) < 0;
    return A < B;
}
pdd get_line_intersection(pdd p,pdd v,pdd q,pdd w){
    
    pdd u = p - q;
    double  t = Cross(w,u)/Cross(v,w);
    return p+v*t;
}
pdd get_line_intersection(Line a,Line b){
    
    return get_line_intersection(a.st,a.ed-a.st,b.st,b.ed-b.st);
}
//  Judge bc Whether the intersection of is in a The right side of the 
bool onright(Line a,Line b,Line c){
    
    pdd o = get_line_intersection(b,c);
    return sgn(area(a.st,a.ed,o)) <= 0; // <= 
}
int q[505];
Line line[505];
int cnt; // cnt  Number of straight lines 
pdd p[505];
double half(){
     //  Half plane intersection , The edges of the intersection are stored in... In counterclockwise order q[] in  !!
    sort(line,line+cnt,cmp);

    int hh = 0,tt = -1;
    for(int i = 0;i < cnt;i++){
    
        if(i && ! dcmp(GetA(line[i]),GetA(line[i-1]))) continue;
        while(hh+1<=tt && onright(line[i],line[q[tt-1]],line[q[tt]])) tt--; //  Judge right 
        while(hh+1<=tt && onright(line[i],line[q[hh]],line[q[hh+1]])) hh++;  //  Judge left 
        q[++tt] = i;
    }
    while(hh+1<= tt && onright(line[q[hh]],line[q[tt-1]],line[q[tt]])) tt--;
    while(hh+1<= tt && onright(line[q[tt]],line[q[hh]],line[q[hh+1]])) hh++;
    q[++tt] = q[hh];

    // TODO WORK
    // double res = 0;
    // vector<pdd> v; 
    // for(int i = hh;i < tt;i++){
    
    // v.push_back(get_line_intersection(line[q[i]],line[q[(i+1)]]));
    // }
    // int len = v.size();
    // for(int i = 1 ; i < len-1;i++){
    
    // res += area(v[0],v[i],v[i+1]);
    // }
    // return res/2.0;
    
}
int n;
int main()
{
    
    cin>>n;
    while(n--){
    
        int t;cin>>t;
        for(int i = 0; i < t;i++) cin>>p[i].x >> p[i].y;
        for(int i  = 0; i < t;i++) line[cnt++] = {
    p[i],p[(i+1)%t]}; 
    }
    // for(int i = 0; i < cnt;i++){
    
    // cout << line[i].st.first <<" "<< line[i].st.second <<" "<< line[i].ed.first<<" "<<line[i].ed.second<< endl;
    // }
    printf("%.3f\n",half());
    return 0;
}