jag_regional_2021_E_riantkb.cpp

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

using fltype = long double;
using itype = long long;

template<typename T>
struct Point {
    T x, y;
    Point() {}
    Point(T x, T y): x(x), y(y) {}
};

vector<fltype> exact_distance_points(const Point<itype>& p, itype r) {
    if (abs(p.y) > r) {
        return {};
    }
    else if (abs(p.y) == r) {
        return { (fltype)p.x };
    }
    else {
        fltype d = sqrt(r * (fltype)r - p.y * (fltype)p.y);
        return { p.x - d, p.x + d };
    }
}

// y が整数のとき壊れそう
vector<fltype> intersect_point(const Point<itype>& frm, const Point<itype>& to, fltype y) {
    if (min(frm.y, to.y) > y || max(frm.y, to.y) < y) {
        return {};
    }
    assert(frm.y != to.y);
    fltype dx = to.x - frm.x;
    fltype dy = to.y - frm.y;
    return { frm.x + (y - frm.y) * dx / dy };
}


vector<fltype> intersect_segment(const Point<itype>& frm, const Point<itype>& to, itype r) {
    if (min(frm.y, to.y) >= r || max(frm.y, to.y) <= -r) {
        return {};
    }
    if (frm.x > to.x) {
        return intersect_segment(to, frm, r);
    }
    if (frm.y == to.y) {
        fltype lx = 1e18;
        fltype rx = -1e18;
        {
            vector<fltype> v = exact_distance_points(frm, r);
            assert(v.size() == 2);
            for (auto& x : v) {
                lx = min(lx, x);
                rx = max(rx, x);
            }
        }
        {
            vector<fltype> v = exact_distance_points(to, r);
            assert(v.size() == 2);
            for (auto& x : v) {
                lx = min(lx, x);
                rx = max(rx, x);
            }
        }
        assert(rx - lx > -1e-9);
        return { lx, rx };
    }
    else {
        fltype lx = 1e18;
        fltype rx = -1e18;
        {
            vector<fltype> v = exact_distance_points(frm, r);
            for (auto& x : v) {
                lx = min(lx, x);
                rx = max(rx, x);
            }
        }
        {
            vector<fltype> v = exact_distance_points(to, r);
            for (auto& x : v) {
                lx = min(lx, x);
                rx = max(rx, x);
            }
        }
        fltype dx = to.x - frm.x;
        fltype dy = to.y - frm.y;
        fltype d = sqrt(dx * dx + dy * dy);
        fltype x1 = frm.x - frm.y * dx / dy - abs(d * r / dy);
        fltype x2 = frm.x - frm.y * dx / dy + abs(d * r / dy);
        fltype t1 = -frm.y / dy - abs(r * dx / d / dy);
        fltype t2 = -frm.y / dy + abs(r * dx / d / dy);
        if (-1e-8 <= t1 && t1 <= 1 + 1e-8) {
            lx = min(lx, x1);
            rx = max(rx, x1);
        }
        if (-1e-8 <= t2 && t2 <= 1 + 1e-8) {
            lx = min(lx, x2);
            rx = max(rx, x2);
        }
        assert(rx - lx > -1e-9);
        return { lx, rx };
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;
    itype r;
    cin >> n >> r;
    vector<Point<itype>> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i].x >> p[i].y;
    }
    vector<pair<fltype, int>> events;
    for (int i = 0; i < n; ++i) {
        vector<fltype> seg = intersect_segment(p[i], p[(i + 1) % n], r);
        if (seg.size()) {
            assert(seg.size() == 2);
            assert(seg[0] < seg[1]);
            events.emplace_back(seg[0], 1);
            events.emplace_back(seg[1], -1);
        }
        vector<fltype> point = intersect_point(p[i], p[(i + 1) % n], 0.5);
        if (point.size()) {
            assert(point.size() == 1);
            events.emplace_back(point[0], 0);
        }
    }
    sort(events.begin(), events.end());
    int isin = 0;
    int intersect_cnt = 0;
    fltype ans = 0;
    for (int i = 0; i + 1 < (int)events.size(); ++i) {
        if (events[i].second == 0) {
            isin ^= 1;
        }
        else {
            intersect_cnt += events[i].second;
        }
        if (isin && intersect_cnt == 0) {
            ans += events[i + 1].first - events[i].first;
        }
    }
    cout << setprecision(16) << ans << '\n';

    return 0;
}