牛客多校第七场 B 题题解

B 题题意：给定平面上一 $nn$ 个点的整点凸多边形，使其绕着任意对称轴在空间中旋转，求其扫过的体积。若无对称轴则输出 $00$。$n\le 1\times 10^{5}n\; \backslash leq\; 1\backslash times\; 10^5$。

解法：由于是整点多边形，因而对称轴至多不超过 $O(\log n)O(\backslash log\; n)$ 条，可以考虑暴力枚举每条多边形的边的中垂线以及点来判定对称轴。更优美的解法（或对于非整点多边形）是使用哈希或者 Manacher 来判定（字符串题与计算几何的第一次交流），具体做法为，找到这个多边形的几何中心 ${\displaystyle (\frac{1}{n}\sum _{i=1}^n{x}_i,\frac{1}{n}\sum _{i=1}^n{y}_i)}\backslash displaystyle\; \backslash left(\; \backslash dfrac\{1\}\{n\}\backslash sum\_\{i=1\}^n\; x\_i,\backslash dfrac\{1\}\{n\}\; \backslash sum\_\{i=1\}^n\; y\_i\backslash right)$，依次记录每个点到几何中心的极角、多边形边长，以点-边-点的顺序得到一个数组并倍长，若存在对称轴则原数组存在一个长度为 $2n-12n-1$ 的回文串。

若对称轴超过两条，则一定是一个以几何中心为球心，半径为几何中心到凸包顶点最远距离的一个球：

上图是以矩形为例。

若对称轴仅一条，则为一旋转体体积，可以根据垂直对称轴方向进行切分，每一段为一圆台体积：${\displaystyle \sum _{i=1}^k\frac{\pi }{3}{h}_i(r_i^2+r_{i-1}^2+r_i{r}_{i-1})}\backslash displaystyle\; \backslash sum\_\{i=1\}^k\; \backslash dfrac\{\backslash pi\}\{3\}h\_i(r\_i^2+r\_\{i-1\}^2+r\_ir\_\{i-1\})$。

注意精度问题，在判断对称轴的时候最好使用 int128。

#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
using T = double;
using db = double;

const db eps = 1e-8, pi = acos(-1);

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

struct Vec {
    T x, y;
    bool operator<(Vec p) const { return tie(x, y) < tie(p.x, p.y); }
    bool operator==(Vec p) const { return tie(x, y) == tie(p.x, p.y); }
    Vec operator+(Vec p) const { return {x + p.x, y + p.y}; }
    Vec operator-(Vec p) const { return {x - p.x, y - p.y}; }
    Vec operator*(T d) const { return {x * d, y * d}; }
    T operator*(Vec p) const { return x * p.x + y * p.y; }
    T cross(Vec p) const { return x * p.y - y * p.x; }
    T cross(Vec a, Vec b) const { return (a - *this).cross(b - *this); }
    Vec operator/(T d) const { return {x / d, y / d}; }
    T len2() const { return x * x + y * y; }
    int onLeft(Vec p) const { return sgn(cross(p)); }
};

using Poly = vector<Vec>; // polygon, points, vectors

struct Line {
    Vec p, v; // point on line, direction vector
    int onLeft(Vec a) const { return v.onLeft(a - p); }
};

vector<Line> polygonAxes(Poly a) {
    int n = a.size(), m = 3 * n;
    a.push_back(a[0]), a.push_back(a[1]);
    vector<pair<T, T>> s(n * 2);
    for (int i = 1, j = 0; i <= n; ++i, j += 2)
        s[j] = {(a[i] - a[i - 1]).len2(), 0},
        s[j + 1] = {a[i].cross(a[i - 1], a[i + 1]), (a[i + 1] - a[i]) * (a[i - 1] - a[i])};
    s.insert(s.end(), s.begin(), s.begin() + n);
    vector<int> f(m), res;
    for (int r = 0, p = 0, i = 0; i < m; i++) {
        f[i] = r > i ? min(r - i, f[p * 2 - i]) : 1;
        while (i >= f[i] && i + f[i] < m && s[i - f[i]] == s[i + f[i]]) ++f[i];
        if (i + f[i] > r) r = i + f[i], p = i;
        if (f[i] > n) res.push_back(i);
    }
    auto get = [&](int i) {
        int x = (i + 1) / 2;
        return i & 1 ? a[x] : (a[x] + a[x + 1]) / 2;
    };
    vector<Line> axe;
    for (auto i : res)
        axe.push_back({get(i), get(i) - get(i - n)});
    return axe;
}

void Solve() {
    int n;
    scanf("%d", &n);
    Poly a(n);
    for (auto &p : a) scanf("%lf%lf", &p.x, &p.y);
    auto axe = polygonAxes(a);
    if (axe.empty()) return puts("0"), void();
    db ans = 0;
    if (axe.size() > 1) {
        db r = 0; Vec o;
        for (auto p : a) o = o + p;
        o = o / n;
        for (auto &p : a) r = max(r, (p - o).len2());
        ans = 4 * r * sqrt(r);
    } else {
        Vec v = axe[0].v, A = axe[0].p;
        a.push_back(a[0]);
        for (int i = 0; i < n; ++i) {
            db r = v.cross(a[i] - A), R = v.cross(a[i + 1] - A);
            if (sgn(r) >= 0 && sgn(R) >= 0)
                ans += (a[i] - a[i + 1]) * v * (r * r + R * R + r * R);
        }
        ans /= v.len2() * sqrt(v.len2());
    }
    printf("%.12lf\n", ans * pi / 3);
}
int main() {
    int t = 1;
    while (t--) Solve();
    return 0;
}