Konveksni Poligoni

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int PARALLEL = 0;
const int CW = 1;
const int CCW = 2;
// polygon tools

class Vector {
public:
    double x, y;
    Vector(double _x, double _y){
        x = _x;
        y = _y;
    }

    double cross(const Vector& v){
        return x * v.y - y * v.x;
    }

    double dot(const Vector& v){
        return x*v.x + y*v.y;
    }
};

class Point {
public:
    double x, y;
    Point(double _x = 0, double _y = 0){
        x = _x;
        y = _y;
    }
};

int orientation(Point p1, Point p2, Point p3){
    double s = (p2.y - p1.y) * (p3.x - p2.x);
    double t = (p2.x - p1.x) * (p3.y - p2.y);
    if(s == t){
        return PARALLEL;
    }
    return s > t ? CW : CCW;
}

bool onSegment(Point p1, Point p2, Point r){
    if(r.x >= min(p1.x,p2.x) && r.x <= max(p1.x,p2.x) && r.y >= min(p1.y,p2.y) && r.y <= max(p1.y,p2.y)){
        return true;
    }
    return false;
}

class Line {
public:
    Point p1, p2;
    Line(double x1 = 0, double y1 = 0, double x2 = 0, double y2 = 0){
        p1 = Point(x1, y1);
        p2 = Point(x2, y2);
    }

    Line(Point _p1, Point _p2){
        p1 = _p1;
        p2 = _p2;
    }

    Point intersection(const Line& l){
        double a1 = p2.y - p1.y;
        double b1 = p1.x - p2.x;
        double c1 = a1*p1.x + b1*p1.y;
        double a2 = l.p2.y - l.p1.y;
        double b2 = l.p1.x - l.p2.x;
        double c2 = a2*l.p1.x + b2*l.p1.y;
        double det = a1 * b2 - a2 * b1;
        if(det == 0){
            return Point(0, 0);
        } else {
            double x = (b2*c1 - b1*c2)/det;
            double y = (a1*c2 - a2*c1)/det;
            return Point(x, y);
        }
    }

    bool intersects(const Line &l){
        int o1 = orientation(p1,p2,l.p1);
        int o2 = orientation(p1,p2,l.p2);
        int o3 = orientation(l.p1,l.p2,p1);
        int o4 = orientation(l.p1,l.p2,p2);
        if(o1 != o2 && o3 != o4){
            return true;
        } else if(o1 == PARALLEL && o2 == PARALLEL && o3 == PARALLEL && o4 == PARALLEL){
            if(onSegment(p1,p2,l.p1) || onSegment(p1,p2,l.p2) || onSegment(l.p1,l.p2,p1) || onSegment(l.p1,l.p2,p2)){
                return true;
            }
        }
        return false;
    }
};

double areaOfPolygon(vector<Point> &points){
    double res = 0;
    for(int i = 1;i<points.size()-1;++i){
        Vector u(points[i].x - points[0].x, points[i].y - points[0].y);
        Vector v(points[i+1].x - points[0].x, points[i+1].y - points[0].y);
        res += u.cross(v);
    }
    return abs(res / 2.0);
}

bool inside(Point a, Line* lines, int n){
    int MAX_TRIES = 1000;
    int MOD = 100007;
    int in = 0, out = 0;
    double maxX = -1e18, maxY = -1e18;
    for(int i = 0;i<n;++i){
        maxX = max(maxX, lines[i].p1.x);
        maxX = max(maxX, lines[i].p2.x);
        maxY = max(maxY, lines[i].p1.y);
        maxY = max(maxY, lines[i].p2.y);
    }
    for(int tries = 0;tries < MAX_TRIES;++tries){
        double px = rand() % (int)MOD + maxX+MOD+1;
        double py = rand() % (int)MOD + maxY+MOD+1;
        Line l(a, Point(px, py));
        int cnt = 0;
        for(int i = 0;i<n;++i){
            if(l.intersects(lines[i])){
                cnt++;
            }
        }
        if(cnt % 2){
            in++;
        } else {
            out++;
        }
    }
    return in > out;
}

double distSq(const Point& a, const Point& b){
    return pow(a.x - b.x, 2) + pow(a.y - b.y, 2);
}

Point refPoint;

int angleCmp(const Point& p1, const Point& p2) {
    int o = orientation(refPoint, p1, p2);
    if (o == 0){
        return (distSq(refPoint, p2) >= distSq(refPoint, p1));
    }
    return (o == CCW);
}

Point nextToLast(stack<Point>& pstack){
    Point prev = pstack.top();
    pstack.pop();
    Point res = pstack.top();
    pstack.push(prev);
    return res;
}

vector<Point> convexHull(vector<Point> points, int n){
    Point first = points[0];
    int minIdx = 0;
    for(int i = 1;i<n;++i){
        if(points[i].y < first.y || (points[i].y == first.y && points[i].x < first.x)){
            first = points[i];
            minIdx = i;
        }
    }
    refPoint = first;
    swap(points[0], points[minIdx]);
    sort(points.begin()+1, points.end(), angleCmp);
    int m = 1;
    for(int i = 1;i<n;++i){
        while(i < n-1 && orientation(refPoint, points[i], points[i+1]) == 0){
            i++;
        }
        points[m] = points[i];
        m++;
    }
    if(m < 3){
        return vector<Point>();
    }
    stack<Point> pstack;
    pstack.push(points[0]);
    pstack.push(points[1]);
    pstack.push(points[2]);
    for(int i = 3;i<m;++i){
        while(orientation(nextToLast(pstack), pstack.top(), points[i]) != CCW){
            pstack.pop();
        }
        pstack.push(points[i]);
    }
    vector<Point> res;
    while(!pstack.empty()){
        res.push_back(pstack.top());
        pstack.pop();
    }
    reverse(res.begin(), res.end());
    return res;
}

double roundTwo(double a){
    double curr = round(a * 100);
    return curr / 100;
}

int main(){
    ios::sync_with_stdio(false);
    srand(time(0));
    int a, b;
    cin>>a>>b;
    Point pa[a], pb[b];
    Line la[a], lb[b];
    for(int i = 0;i<a;++i){
        int x,y;
        cin>>x>>y;
        pa[i] = Point(x, y);
    }
    for(int i = 0;i<b;++i){
        int x,y;
        cin>>x>>y;
        pb[i] = Point(x, y);
    }
    for(int i = 0;i<a;++i){
        la[i] = Line(pa[i], pa[(i+1) % a]);
    }
    for(int i = 0;i<b;++i){
        lb[i] = Line(pb[i], pb[(i+1) % b]);
    }
    vector<Point> insidePoints;
    for(int i = 0;i<a;++i){
        for(int j = 0;j<b;++j){
            if(la[i].intersects(lb[j])){
                insidePoints.push_back(la[i].intersection(lb[j]));
            }
        }
    }
    for(int i = 0;i<a;++i){
        if(inside(pa[i], lb, b)){
            insidePoints.push_back(pa[i]);
        }
    }
    for(int i = 0;i<b;++i){
        if(inside(pb[i], la, a)){
            insidePoints.push_back(pb[i]);
        }
    }
    vector<Point> ch;
    if(insidePoints.size() > 2){
        ch = convexHull(insidePoints, insidePoints.size());
    }
    double res = 0;
    if(ch.size() >= 3){
        res = areaOfPolygon(ch) ;
    }
    cout<<roundTwo(res)<<endl;
    return 0;
}