TEAMBOOK пересечение полуплоскостей

#include <bits/stdc++.h>
using ld = double;
using ll = long long;
#define double ld
#define long ll
#define all(x) begin(x), end(x)
using namespace std;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

struct Point {
    double x, y;
    Point(double a, double b) : x(a), y(b) {}
    Point() : x(0), y(0) {}
};
istream &operator>>(istream &in, Point &p) {
    int x, y;
    in >> x >> y;
    p.x = x;
    p.y = y;
    return in;
}
ostream &operator<<(ostream &out, Point p) {
    return out << p.x << " " << p.y;
}
double operator%(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}
double operator*(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}
Point operator*(Point a, double k) {
    return {a.x * k, a.y * k};
}
Point operator-(Point a, Point b) {
    return {a.x - b.x, a.y - b.y};
}
Point vec(Point a, Point b) {
    return {b.x - a.x, b.y - a.y};
}
Point operator+(Point a, Point b) {
    return {a.x + b.x, a.y + b.y};
}
double turn(Point a, Point b, Point c) {
    return vec(a, b) % vec(a, c);
}
Point inter(Point a, Point b, Point c, Point d) {
    double acd = (vec(a, c) % vec(a, d)) / 2;
    double bdc = (vec(b, d) % vec(b, c)) / 2;
    double s = acd + bdc;
    return a + vec(a, b) * (acd / s);
}
struct Half {
    Point a, b;
    Half(Point x, Point y) : a(x), b(y) {}
    Half() : a(), b() {}
};
istream &operator>>(istream &in, Half &p) {
    return in >> p.a >> p.b;
}
ostream &operator<<(ostream &out, Half p) {
    return out << "HP: " << p.a << " " << p.b;
}
Point inter(Half a, Half b) {
    return inter(a.a, a.b, b.a, b.b);
}
bool inside(Point o, Half a) {
    return turn(a.a, a.b, o) >= 0;
}
bool collinear(Half a, Half b) {
    Point v = vec(a.a, a.b);
    Point u = vec(b.a, b.b);
    return v % u == 0;
}
bool sameDir(Half a, Half b) {
    Point v = vec(a.a, a.b);
    Point u = vec(b.a, b.b);
    return v * u >= 0;
}
int getPlane(double x, double y) {
    if ((x < 0 && y == 0) || y < 0) {
        return -1;
    } else {
        return 1;
    }
}
bool operator<(Half a, Half b) {
    Point v = vec(a.a, a.b);
    Point u = vec(b.a, b.b);
    int vp = getPlane(v.x, v.y), up = getPlane(u.x, u.y);
    if (vp != up) {
        return vp < up;
    } else {
        return v % u > 0;
    }
}
const int N = 1e5;
int hpcnt, sz;
Half h[N];
Half st[N];
Point hpres[N];

bool worse(Half a, Half b) {
    return collinear(a, b) && sameDir(a, b) && inside(b.a, a);
}
bool bad(Half a, Half b, Half c) {
    Point p = inter(b, c);
    return !inside(p, a);
}

void addHP(Half a) {
    h[hpcnt++] = a;
}

void initHP() {
    sz = 0;
    hpcnt = 0;
    const double S = 3e5;
    addHP({{-S, -S}, {+S, -S}});
    addHP({{+S, -S}, {+S, +S}});
    addHP({{+S, +S}, {-S, +S}});
    addHP({{-S, +S}, {-S, -S}});
}

void process(int i, bool push) {
    if (sz >= 1 && worse(h[i], st[sz - 1])) {
        return;
    }
    if (sz >= 1 && worse(st[sz - 1], h[i])) {
        --sz;
    }
    while (sz >= 2 && bad(st[sz - 2], st[sz - 1], h[i])) {
        --sz;
    }
    if (push) {
        st[sz++] = h[i];
    }
}

void solveHP() {
    stable_sort(h, h + hpcnt);
    sz = 0;
    for (int i = 0; i < hpcnt; ++i) {
        process(i, true);
    }
    for (int i = 0; i < hpcnt; ++i) {
        process(i, true);
    }
    int l = -1, r = -1;
    map<tuple<int, int, int, int>, int> was;
    for (int i = 0; i < sz; ++i) {
        int a = (int)st[i].a.x, b = (int)st[i].a.y, c = (int)st[i].b.x, d = (int)st[i].b.y;
        tuple<int, int, int, int> pp(a, b, c, d);
        if (was.count(pp)) {
            l = was[pp];
            r = i;
            break;
        }
        was[pp] = i;
    }
    sz = r - l;
    for (int i = l; i < r; ++i) {
        hpres[i - l] = inter(st[i], st[i + 1]);
    }
}

int n;
Point p[N];

double dist(Point a, Point b) {
    return hypot(a.x - b.x, a.y - b.y);
}


double query(Point q) {
    initHP();
    for (int i = 0, l = i + 1; i < n; ++i) {
        while (turn(p[i], p[l], q) >= 0) {
            ++l;
        }
        --l;
        addHP(Half(p[i], p[l]));
    }
    solveHP();
    double answer = 0;
    for (int i = 0; i < sz; ++i) {
        answer = max(answer, dist(q, hpres[i]));
    }
    return answer;
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        p[i + n] = p[i];
    }
    int m;
    cin >> m;
    while (m--) {
        Point q;
        cin >> q;
        cout << query(q) << "\n";
    }
    return 0;
}