Problem: Example

Input

4 6 5
-2 5
-2 -1
2 -1
2 5
-2 1
-2 0
0 0
0 -2
2 -2
2 1


Output

8

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

using D = double;
const D PI = acos(D(-1)), EPS = 1e-10;

const int MD = 10010;
using Pi = pair<int, int>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);

    int n, m, L;
    cin >> n >> m >> L;
    V<Pi> p1(n), p2(m);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        p1[i] = Pi(x, y);
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        p2[i] = Pi(x, y);
    }
    auto add = [&](V<Pi> v) {
        sort(begin(v), end(v), [&](Pi a, Pi b) {
            return a.first < b.first;
        });
        V<Pi> res;
        for (auto p: v) {
            if (res.size() && res.back().second >= p.first) {
                res.back().second = max(res.back().second, p.second);
                continue;
            }
            res.push_back(p);
        }
        return res;
    };
    auto mul = [&](V<Pi> v1, V<Pi> v2) {
        V<Pi> res;
        while (v1.size() && v2.size()) {
            Pi x = v1.back(), y = v2.back();
            if (y.second < x.first) {
                v1.pop_back();
                continue;
            }
            if (x.second < y.first) {
                v2.pop_back();
                continue;
            }
            res.push_back(Pi(max(x.first, y.first), min(x.second, y.second)));
            if (x.first > y.first) {
                v1.pop_back();
            } else {
                v2.pop_back();
            }
        }
        sort(begin(res), end(res), [](Pi a, Pi b){
            return a.first < b.first;
        });
        return res;
    };

    ll ans = 0;
    for (int y = -MD; y <= MD; y++) {
        V<Pi> crs;
        V<int> crsxv;
        for (int i = 0; i < m; i++) {
            Pi a = p2[i], b = p2[(i+1)%m];
            if (a.first == b.first) {
                if (min(a.second, b.second) <= y && y < max(a.second, b.second)) {
                    crsxv.push_back(a.first);
                }
            }            
            if (a.first == b.first) {
                // horizon
                int lw = a.second - y, up = b.second - y;
                if (lw > up) swap(lw, up);
                if (up < 0) {
                    swap(lw, up); lw = -lw; up = -up;
                }
                if (lw < 0) {
                    up = max(up, -lw);
                    lw = 0;
                }
                if (lw > L) continue;
                up = min(up, L);
                int dima = int(sqrt(L*L-lw*lw) + (1e-9));
                int dimi = int(sqrt(L*L-up*up) - (1e-9)) + 1;
                if (dimi > dima) continue;
                int x = a.first;
                crs.push_back(Pi(x-dima, x-dimi));
                crs.push_back(Pi(x+dimi, x+dima));                
            } else {
                int lw = a.first, up = b.first;
                if (lw > up) swap(lw, up);
                int l = abs(y - a.second);
                if (l > L) continue;
                int di1 = int(sqrt(L*L - l*l) + (1e-9));
                int di2 = int(sqrt(L*L - l*l) - (1e-9)) + 1;
                assert(di2 >= di1);
                crs.push_back(Pi(lw-di1, up-di2));
                crs.push_back(Pi(lw+di2, up+di1));
            }
        }
        sort(begin(crsxv), end(crsxv), greater<int>());
        while (crsxv.size()) {
            int lw = crsxv.back(); crsxv.pop_back();
            int up = crsxv.back(); crsxv.pop_back();
            if (up-lw < L) continue;
            crs.push_back(Pi(lw, up-L));
            crs.push_back(Pi(lw+L, up));
        }

        crs = add(crs);

        V<int> xv1, xv2;
        for (int i = 0; i < n; i++) {
            Pi a = p1[i], b = p1[(i+1 < n) ? i+1 : 0];
            if (a.first == b.first) {
                if (min(a.second, b.second) <= y && y < max(a.second, b.second)) {
                    xv1.push_back(a.first);
                }
                if (min(a.second, b.second) < y && y <= max(a.second, b.second)) {
                    xv2.push_back(a.first);
                }
            }
        }
        sort(begin(xv1), end(xv1), greater<int>());
        sort(begin(xv2), end(xv2), greater<int>());
        assert(int(xv1.size()) % 2 == 0);
        assert(int(xv2.size()) % 2 == 0);
        V<Pi> base1, base2;
        while (xv1.size()) {
            int lw = xv1.back()+1; xv1.pop_back();
            int up = xv1.back()-1; xv1.pop_back();
            if (lw > up) continue;
            base1.push_back(Pi(lw, up));
        }
        while (xv2.size()) {
            int lw = xv2.back()+1; xv2.pop_back();
            int up = xv2.back()-1; xv2.pop_back();
            if (lw > up) continue;
            base2.push_back(Pi(lw, up));
        }
        V<Pi> base = mul(base1, base2);
        
        for (auto pi: base) {
            ans += pi.second - pi.first + 1;
        }
        V<Pi> lst = mul(crs, base);
        for (auto pi: lst) {
            ans -= pi.second - pi.first + 1;
        }
/*        cout << "X " << y << " " << ans << endl;
        if (base.size()) {
            cout << "RNG: " << y << " : ";
            for (auto pi: base) {
                cout << "(" << pi.first << ", " << pi.second << "), ";
            }
            cout << endl;
            for (auto pi: crs) {
                cout << "(" << pi.first << ", " << pi.second << "), ";
            }
            cout << endl;
            for (auto pi: lst) {
                cout << "(" << pi.first << ", " << pi.second << "), ";
            }
            cout << endl;
        }*/
    }
    cout << ans << endl;
    return 0;
}