Geometry

base.cpp

/** Constants Start **/
const double PI = acos(-1.0);
const double EPS = 1e-8;
const double INF = 1e9 + 5;
template <typename T> int sgn(T x) { return x < -EPS ? -1 : x > EPS; }
/** Constants End **/
/** Base Start **/
struct pt {
    T x, y;
    pt operator+(pt p) { return {x + p.x, y + p.y}; }
    pt operator-(pt p) { return {x - p.x, y - p.y}; }
    pt operator-() { return {-x, -y}; }
    pt operator*(pt p) { return {x * p.x, y * p.y}; }
    pt operator*(T d) { return {x * d, y * d}; }
    pt operator/(T d) { return {x / d, y / d}; }
    bool operator==(pt p) { return x == p.x && y == p.y; }
    bool operator!=(pt p) { return !(*this == p); }
    bool operator<(pt p) const { return make_pair(x, y) < make_pair(p.x, p.y); }
    bool operator>(pt p) { return p < *this; }
    T sq() { return x * x + y * y; }
    double abs() { return sqrt(sq()); }
    pt translate(pt v) { return *this + v; }
    pt perp() { return {-y, x}; }
    pt rot(double a) { return {x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)}; }
};
ostream &operator<<(ostream &os, pt p) { return cout << "(" << p.x << "," << p.y << ")"; }
istream &operator>>(istream &is, pt p) { return cin >> p.x >> p.y; }
pt scale(pt c, double factor, pt p) { return c + (p - c) * factor; }
T dot(pt v, pt w) { return v.x * w.x + v.y * w.y; }
T cross(pt v, pt w) { return v.x * w.y - v.y * w.x; }
T orient(pt a, pt b, pt c) { return cross(b - a, c - a); }
int orientS(pt a, pt b, pt c) { return sgn(orient(a, b, c)); }
T orient(pt b, pt c) { return cross(b, c); }
bool half(pt p) {
    assert(p.x != 0 || p.y != 0);
    return p.y > 0 || (p.y == 0 && p.x < 0);
}
auto polarCmp(pt o = {0, 0}) {
    return [o](pt v, pt w) { return make_tuple(half(v - o), 0, v.sq()) < make_tuple(half(w - o), cross(v - o, w - o), w.sq()); };
}
struct line {
    pt v;
    T c;
    line() {}
    // From direction vector v and offset c
    line(pt v, T c) : v(v), c(c) { assert(v.sq() != 0); }
    // From equation ax+by=c
    line(T a, T b, T c) : v({b, -a}), c(c) { assert(v.sq() != 0); }
    // From points P and Q
    line(pt p, pt q) : v(q - p), c(cross(v, p)) { assert(v.sq() != 0); }
    // - these work with T = int
    T side(pt p) { return cross(v, p) - c; }
    double dist(pt p) { return abs(side(p)) / v.abs(); }
    double sqDist(pt p) { return side(p) * side(p) / (double)v.sq(); }
    line perpThrough(pt p) { return {p, p + v.perp()}; }
    bool cmpProj(pt p, pt q) { return dot(v, p) < dot(v, q); }
    line translate(pt t) { return {v, c + cross(v, t)}; }
    // - these require T = double
    line shiftLeft(double dist) { return {v, c + dist * v.abs()}; }
    pt proj(pt p) { return p - v.perp() * side(p) / v.sq(); }
    pt refl(pt p) { return p - v.perp() * 2 * side(p) / v.sq(); }
};
pair<bool, pt> inter(line l1, line l2) {
    T d = cross(l1.v, l2.v);
    if (d == 0)
        return {false, pt{0, 0}};
    return {true, (l2.v * l1.c - l1.v * l2.c) / d}; // requires floating-point coordinates
}
bool properInter(pt a, pt b, pt c, pt d, pt &out) {
    double oa = orient(c, d, a), ob = orient(c, d, b), oc = orient(a, b, c), od = orient(a, b, d);
    if (sgn(oa) * sgn(ob) < 0 && sgn(oc) * sgn(od) < 0) {
        out = (a * ob - b * oa) / (ob - oa);
        return true;
    }
    return false;
}
bool inDisk(pt a, pt b, pt p) { return dot(a - p, b - p) <= 0; }
bool onSegment(pt a, pt b, pt p) { return orientS(a, b, p) == 0 && inDisk(a, b, p); }
/** Base End **/

circle.cpp

/* Circle Start */
struct circle {
    pt c;
    double r;
};
pt circumCenter(pt a, pt b, pt c) {
    b = b - a, c = c - a;     // consider coordinates relative to A
    assert(cross(b, c) != 0); // no circumcircle if A,B,C aligned
    return a + (b * c.sq() - c * b.sq()).perp() / cross(b, c) / 2;
}
double circumRadius(pt a, pt b, pt c) { return (a - b).abs() * (b - c).abs() * (c - a).abs() / abs(orient(a, b, c)) / 2.; }
circle circumCircle(pt a, pt b, pt c) { return {circumCenter(a, b, c), circumRadius(a, b, c)}; }
int circleLine(circle c, line l, pair<pt, pt> &out) {
    double h2 = c.r * c.r - l.sqDist(c.c);
    if (h2 >= 0) {                         // the line touches the circle
        pt p = l.proj(c.c);                // point P
        pt h = l.v * sqrt(h2) / l.v.abs(); // vector parallel to l, of length h
        out = {p - h, p + h};
    }
    return 1 + sgn(h2);
}
int circleCircle(circle c1, circle c2, pair<pt, pt> &out) {
    pt d = c2.c - c1.c;
    double d2 = d.sq();
    if (d2 == 0) { // concentric circles
        assert(c1.r != c2.r);
        return 0;
    }
    double pd = (d2 + c1.r * c1.r - c2.r * c2.r) / 2; // = |O_1P| * d
    double h2 = c1.r * c1.r - pd * pd / d2;           // = hˆ2
    if (h2 >= 0) {
        pt p = c1.c + d * pd / d2, h = d.perp() * sqrt(h2 / d2);
        out = {p - h, p + h};
    }
    return 1 + sgn(h2);
}
int tangents(circle c1, circle c2, bool inner, vector<pair<pt, pt>> &out) {
    if (inner)
        c2.r = -c2.r;
    pt d = c2.c - c1.c;
    double dr = c1.r - c2.r, d2 = d.sq(), h2 = d2 - dr * dr;
    if (d2 == 0 || h2 < 0) {
        assert(h2 != 0);
        return 0;
    }
    for (int sign : {-1, 1}) {
        pt v = (d * dr + d.perp() * sqrt(h2) * sign) / d2;
        out.push_back({c1.c + v * c1.r, c2.c + v * c2.r});
    }
    return 1 + (h2 > 0);
}

// IMPORTANT: random_shuffle(pts.begin(), pts.end())
circle MEC(vector<pt> &pts, vector<pt> ch = {}) { // Minimum Enclosing Circle
    if (pts.empty() || ch.size() == 3) {
        if (ch.size() == 0)
            return {0, -1};
        else if (ch.size() == 1)
            return {ch[0], 0};
        else if (ch.size() == 2)
            return {(ch[0] + ch[1]) / 2, (ch[0] - ch[1]).abs() / 2};
        else
            return circumCircle(ch[0], ch[1], ch[2]);
    }
    auto p = pts.back();
    pts.pop_back();
    auto c = MEC(pts, ch);
    if (sgn((p - c.c).abs() - c.r) > 0) {
        ch.push_back(p);
        c = MEC(pts, ch);
    }
    pts.push_back(p);
    return c;
}
/* Circle End */

convex.cpp

/* Convex Start */
vector<pt> convexHull(vector<pt> &pts) { // O(n log n)
    sort(pts.begin(), pts.end());
    vector<pt> hull;
    for (int phase = 0; phase < 2; ++phase) {
        auto start = hull.size();
        for (auto &point : pts) {
            while (hull.size() >= start + 2 && orientS(hull[hull.size() - 2], hull.back(), point) <= 0)
                hull.pop_back();
            hull.push_back(point);
        }
        hull.pop_back();
        reverse(pts.begin(), pts.end());
    }
    if (hull.size() == 2 && hull[0] == hull[1])
        hull.pop_back();
    return hull;
}
// if strict, returns false when A is on the boundary.
bool inConvex(vector<pt> &l, pt p, bool strict = true) { // O(log n)
    int a = 1, b = l.size() - 1, c;
    if (orientS(l[0], l[a], l[b]) > 0)
        swap(a, b);
    if (orientS(l[0], l[a], p) > 0 || orientS(l[0], l[b], p) < 0 || (strict && (orientS(l[0], l[a], p) == 0 || orientS(l[0], l[b], p) == 0)))
        return false;
    while (abs(a - b) > 1) {
        c = (a + b) / 2;
        if (orientS(l[0], l[c], p) > 0)
            b = c;
        else
            a = c;
    }
    return orientS(l[a], l[b], p) < 0 ? true : !strict;
}
// Max distance across a convex polygon
T convexDiameter(vector<pt> poly) { // O(n)
    int n = poly.size();
    auto res = T(0);
    for (int i = 0, j = n < 2 ? 0 : 1; i < j; ++i)
        for (;; j = (j + 1) % n) {
            res = max(res, (poly[i] - poly[j]).sq());
            if (orientS({0, 0}, poly[(j + 1) % n] - poly[j], poly[i + 1] - poly[i]) >= 0)
                break;
        }
    return res;
}
vector<pt> convexConvex(vector<pt> &P, vector<pt> &Q) { // O(log n)
    const int n = P.size(), m = Q.size();
    int a = 0, b = 0, aa = 0, ba = 0;
    enum { Pin, Qin, Unknown } in = Unknown;
    vector<pt> R;
    do {
        int a1 = (a + n - 1) % n, b1 = (b + m - 1) % m;
        double C = cross(P[a] - P[a1], Q[b] - Q[b1]);
        double A = cross(P[a1] - Q[b], P[a] - Q[b]);
        double B = cross(Q[b1] - P[a], Q[b] - P[a]);
        pt r;
        if (properInter(P[a1], P[a], Q[b1], Q[b], r)) {
            if (in == Unknown)
                aa = ba = 0;
            R.push_back(r);
            in = B > 0 ? Pin : (A > 0 ? Qin : in);
        }
        if (C == 0 && B == 0 && A == 0) {
            if (in == Pin) {
                b = (b + 1) % m;
                ++ba;
            } else {
                a = (a + 1) % m;
                ++aa;
            }
        } else if ((C >= 0 && A > 0) || (C < 0 && B <= 0)) {
            if (in == Pin)
                R.push_back(P[a]);
            a = (a + 1) % n;
            ++aa;
        } else {
            if (in == Qin)
                R.push_back(Q[b]);
            b = (b + 1) % m;
            ++ba;
        }
    } while ((aa < n || ba < m) && aa < 2 * n && ba < 2 * m);
    if (in == Unknown) {
        if (inConvex(Q, P[0]))
            return P;
        if (inConvex(P, Q[0]))
            return Q;
    }
    return R;
}
/** Convex End **/

halfplane.cpp

bool checkhp(line &a, line &b, line &me) { return sgn(me.side(inter(a, b).second)) > 0; }
vector<pt> halfPlaneIntersection(vector<line> border) { // O(n log n): Finds convex polygon of intersecting half planes.
    border.push_back(line{pt{-INF, -INF}, pt{INF, -INF}});
    border.push_back(line{pt{INF, -INF}, pt{INF, INF}});
    border.push_back(line{pt{INF, INF}, pt{-INF, INF}});
    border.push_back(line{pt{-INF, INF}, pt{-INF, -INF}});

    sort(border.begin(), border.end(), [](auto a, auto b) { return polarCmp()(a.v, b.v); });
    auto eq = [](line a, line b) { return sgn(atan2(a.v.y, a.v.x) - atan2(b.v.y, b.v.x)) == 0; };
    border.resize(unique(border.begin(), border.end(), eq) - border.begin());
    deque<line> deq;
    for (int i = 0; i < border.size(); ++i) {
        line cur = border[i];
        while (deq.size() > 1 && !checkhp(deq[deq.size() - 2], deq[deq.size() - 1], cur))
            deq.pop_back();
        while (deq.size() > 1 && !checkhp(deq[0], deq[1], cur))
            deq.pop_front();
        deq.push_back(cur);
    }
    while (deq.size() > 1 && !checkhp(deq[deq.size() - 2], deq[deq.size() - 1], deq[0]))
        deq.pop_back();

    vector<pt> pts;
    for (int i = 0; i < deq.size(); i++)
        pts.push_back(inter(deq[i], deq[(i + 1) % deq.size()]).second);
    return pts;
}

polygon.cpp

/* Polygon Start */
double areaTriangle(pt a, pt b, pt c) { return abs(cross(b - a, c - a)) / 2.0; }
double areaPolygon(vector<pt> p) { // if negative, p is in clock-wise order.
    double area = 0.0;
    for (int i = 0, n = p.size(); i < n; i++)
        area += cross(p[i], p[(i + 1) % n]); // wrap back to 0 if i == n -1
    return area / 2.0;
}
// true if P at least as high as A (blue part)
bool above(pt a, pt p) { return p.y >= a.y; }
// check if [PQ] crosses ray from A
bool crossesRay(pt a, pt p, pt q) { return (above(q, a) - above(p, a)) * orient(a, p, q) > 0; }
// if strict, returns false when A is on the boundary
bool inPolygon(vector<pt> &p, pt a, bool strict = true) { // O(n)
    int numCrossings = 0;
    for (int i = 0, n = p.size(); i < n; i++) {
        if (onSegment(p[i], p[(i + 1) % n], a))
            return !strict;
        numCrossings += crossesRay(a, p[i], p[(i + 1) % n]);
    }
    return numCrossings & 1; // inside if odd number of crossings
}
/* Polygon End */

polygon_union.cpp

#include <bits/stdc++.h>
using namespace std;

using db = double;
const db eps = 1e-8;

struct pt {
    db x, y;
    pt(db x = 0, db y = 0) : x(x), y(y) {}
};

inline int sgn(db x) { return (x > eps) - (x < -eps); }

pt operator-(pt p1, pt p2) { return pt(p1.x - p2.x, p1.y - p2.y); }

db vect(pt p1, pt p2) { return p1.x * p2.y - p1.y * p2.x; }

db scal(pt p1, pt p2) { return p1.x * p2.x + p1.y * p2.y; }

db polygon_union(vector<pt> poly[], int n) {
    auto ratio = [](pt A, pt B, pt O) {
        return !sgn(A.x - B.x) ? (O.y - A.y) / (B.y - A.y) : (O.x - A.x) / (B.x - A.x);
    };
    db ret = 0;
    for (int i = 0; i < n; ++i) {
        for (int v = 0; v < poly[i].size(); ++v) {
            pt A = poly[i][v], B = poly[i][(v + 1) % poly[i].size()];
            vector<pair<db, int>> segs;
            segs.emplace_back(0, 0), segs.emplace_back(1, 0);
            for (int j = 0; j < n; ++j)
                if (i != j) {
                    for (size_t u = 0; u < poly[j].size(); ++u) {
                        pt C = poly[j][u], D = poly[j][(u + 1) % poly[j].size()];
                        int sc = sgn(vect(B - A, C - A)), sd = sgn(vect(B - A, D - A));
                        if (!sc && !sd) {
                            if (sgn(scal(B - A, D - C)) > 0 && i > j) {
                                segs.emplace_back(ratio(A, B, C), 1), segs.emplace_back(ratio(A, B, D), -1);
                            }
                        } else {
                            db sa = vect(D - C, A - C), sb = vect(D - C, B - C);
                            if (sc >= 0 && sd < 0)
                                segs.emplace_back(sa / (sa - sb), 1);
                            else if (sc < 0 && sd >= 0)
                                segs.emplace_back(sa / (sa - sb), -1);
                        }
                    }
                }
            sort(segs.begin(), segs.end());
            db pre = min(max(segs[0].first, 0.0), 1.0), now, sum = 0;
            int cnt = segs[0].second;
            for (int j = 1; j < segs.size(); ++j) {
                now = min(max(segs[j].first, 0.0), 1.0);
                if (!cnt)
                    sum += now - pre;
                cnt += segs[j].second;
                pre = now;
            }
            ret += vect(A, B) * sum;
        }
    }
    return ret / 2;
}

const int N = 110;
vector<pt> v[N];

int main() {
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    db sum = 0;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        v[i].resize(m);
        for (int j = 0; j < m; j++)
            cin >> v[i][j].x >> v[i][j].y;
        db cur = 0;
        for (int j = 0; j < m; j++) {
            cur += vect(v[i][j], v[i][(j + 1) % m]);
        }
        if (cur < 0)
            reverse(v[i].begin(), v[i].end());
        sum += fabs(cur);
    }
    cout << sum / 2 << ' ' << polygon_union(v, n) << endl;
}

segment.cpp

/** Line Segment Start **/
set<pt> inters(pt a, pt b, pt c, pt d) {
    pt out;
    if (properInter(a, b, c, d, out))
        return {out};
    set<pt> s;
    if (onSegment(c, d, a) == true)
        s.insert(a);
    if (onSegment(c, d, b))
        s.insert(b);
    if (onSegment(a, b, c))
        s.insert(c);
    if (onSegment(a, b, d))
        s.insert(d);
    return s;
}
double segPoint(pt a, pt b, pt p) {
    if (a != b) {
        line l(a, b);
        if (l.cmpProj(a, p) && l.cmpProj(p, b)) // if closest to projection
            return l.dist(p);                   // output distance to line
    }
    return min((p - a).abs(), (p - b).abs()); // otherwise distance to A or B
}
double segSeg(pt a, pt b, pt c, pt d) {
    pt dummy;
    if (properInter(a, b, c, d, dummy))
        return 0;
    return min({segPoint(a, b, c), segPoint(a, b, d), segPoint(c, d, a), segPoint(c, d, b)});
}
/** Line Segment End **/