P6818 [PA2013]Działka 题解

jiangly · 2020-09-19 12:22:19 · 题解

首先可以扫描线 + 线段树求出每个询问四个方向的第一个点，通过这些点把询问拆成四个方向的凸包。

预处理每对点逆时针沿凸包走的叉积和 (如左下到右上就是沿右下凸包走)。每个询问将四个方向求和再除以 2 即可。

时间复杂度 O(n^2+m\log m)。

#include <bits/stdc++.h>

constexpr int N = 3e3, M = 1e6, S = 1 << 21;

int n, m, k;
struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
} p[N];
bool operator<(const Point &lhs, const Point &rhs) {
    return lhs.x != rhs.x ? lhs.x < rhs.x : lhs.y < rhs.y;
}
int64_t cross(const Point &lhs, const Point &rhs) {
    return 1ll * lhs.x * rhs.y - 1ll * lhs.y * rhs.x;
}
Point operator-(const Point &lhs, const Point &rhs) {
    return Point(lhs.x - rhs.x, lhs.y - rhs.y);
}

int a[N];
int64_t f[N][N];

int xl[M], xr[M], yl[M], yr[M];
int b[M];
int pt[M][4];

int lg;
int arr[S];

void modify(int x, int v) {
    for (x += (1 << lg) + 1; x; x /= 2)
        arr[x] = std::min(arr[x], v);
}

int rangeMin(int l, int r) {
    int res = n;
    for (l += (1 << lg), r += (1 << lg) + 2; l ^ r ^ 1; l /= 2, r /= 2) {
        if (l % 2 == 0)
            res = std::min(res, arr[l ^ 1]);
        if (r % 2 == 1)
            res = std::min(res, arr[r ^ 1]);
    }
    return res;
}

void work(int id, int offset = 0) {
    std::iota(a, a + n, 0);
    std::sort(a, a + n, [&](int i, int j) {
        return p[i] < p[j];
    });

    std::iota(b, b + m, 0);
    std::sort(b, b + m, [&](int i, int j) {
        return xl[i] > xl[j];
    });

    std::fill(arr, arr + (1 << (lg + 1)), n);

    for (int i = n - 1, qi = 0; i >= 0; --i) {
        int u = a[i];
        int w = u;
        for (int j = i + 1; j < n; ++j) {
            int v = a[j];
            if (p[v].y < p[u].y)
                continue;
            if (cross(p[w] - p[u], p[v] - p[u]) <= 0)
                w = v;
            f[u][v] = cross(p[u], p[w]) + f[w][v];
        }

        modify(p[u].y + offset, i);

        int lim = i == 0 ? -k - 1 : p[a[i - 1]].x;
        while (qi < m && xl[b[qi]] > lim) {
            int j = b[qi];
            pt[j][id] = a[rangeMin(yl[j] + offset, yr[j] + offset)];
            ++qi;
        }
    }
}

void rotate() {
    for (int i = 0; i < n; ++i) {
        std::swap(p[i].x, p[i].y);
        p[i].x = -p[i].x;
    }
    for (int i = 0; i < m; ++i) {
        std::swap(xl[i], yl[i]);
        std::swap(xr[i], yr[i]);
        std::swap(xl[i], xr[i]);
        xl[i] = -xl[i];
        xr[i] = -xr[i];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> k >> n;
    while ((1 << lg) < k + 3)
        ++lg;
    for (int i = 0; i < n; ++i)
        std::cin >> p[i].x >> p[i].y;
    std::cin >> m;
    for (int i = 0; i < m; ++i)
        std::cin >> xl[i] >> xr[i] >> yl[i] >> yr[i];

    work(0);
    rotate();
    work(3);
    rotate();
    work(2, k);
    rotate();
    work(1, k);

    for (int i = 0; i < m; ++i) {
        int64_t area = 0;
        for (int j = 0; j < 4; ++j)
            area += f[pt[i][j]][pt[i][(j + 1) % 4]];
        std::cout << area / 2 << "." << "05"[area % 2] << "\n";
    }

    return 0;
}