2025-沈阳站-区域赛-G. Collision Damage（正式开始攻克计算几何）（两个形状在所有可能的平移下的交集面积的积分，等于两个面积的和）（minkowski 即合成大凸包）

题目大意

在一个基于2D物理的视频游戏中，两个角色$P$和$Q$在战场上移动。每个角色都由一个凸多边形表示，用作其碰撞箱。当两个碰撞箱重叠时，游戏会计算它们的交集区域作为碰撞伤害。

然而，由于竞技场中不可预测的风流，在任意平移向量$\mathbf{t} = (t_x, t_y)$的作用下，角色$Q$可以被位移，但不能旋转或翻转。您需要计算当$Q$均匀随机放置以确实与$P$发生碰撞时的预期碰撞伤害，即它们的交集具有正面积。

更正式地，定义$f(\mathbf{t})$为表示角色$P$的多边形和表示角色$Q$的多边形在沿$\mathbf{t}$平移后的交集区域的面积。设$D \subseteq \mathbb{R}^2$为所有平移向量$\mathbf{t}$的集合，使得$f(\mathbf{t}) > 0$。可以证明$D$具有正面积，记为$|D|$。您需要计算$\frac{1} {|D|} \iint\limits_{D} f(\mathbf{t}) \, d\mathbf{t}$。

思路讲解

1. 分子分析 ($\iint_D f(\mathbf{t}) \, d\mathbf{t}$)

根据积分几何中的运动学公式，两个形状在所有可能的平移下的交集面积的积分，等于这两个形状面积的乘积。

$$\iint_{\mathbb{R}^2} \text{Area}(P \cap Q(\mathbf{t})) \, d\mathbf{t} = \text{Area}(P) \times \text{Area}(Q)$$

因此，分子只需计算两个多边形面积的乘积。

原因可以用以下离散化像素法解释：

想象一下，我们将 $P$ 和 $Q$ 都放在一个非常细的网格纸上，把它们看作是由无数个微小的像素点组成的。

• 假设 $P$ 由 $N$ 个像素点组成（代表面积 $S_P$）。

• 假设 $Q$ 由 $M$ 个像素点组成（代表面积 $S_Q$）。

我们要求的积分 $\iint \text{Area}(P \cap Q(\mathbf{t})) \, d\mathbf{t}$，本质上是在问：当我们把 $Q$ 移动到所有可能的位置时，总共有多少次“像素重叠”发生？

让我们换个角度思考：

1. 取 $Q$ 中的任意一个特定像素点 $q_0$。

2. 当 $Q$ 在平面上到处移动时，这个点 $q_0$ 会经过平面的每一个位置。

3. 它什么时候会和 $P$ 发生“重叠”？也就是当 $q_0$ 落在 $P$ 内部的时候。

4. 因为 $P$ 有 $N$ 个像素，所以 $q_0$ 会在 $N$ 个不同的位置（平移向量）上为“总重叠面积”贡献 1 个单位。

5. 现在，对 $Q$ 中的每一个像素点都重复这个过程。$Q$ 总共有 $M$ 个像素点。

6. 因此，总的重叠贡献 = ($Q$ 的像素数) $\times$ ($P$ 的像素数) = $M \times N$。

这就对应了 $\text{Area}(Q) \times \text{Area}(P)$。

总的来说，就是以 $Q$ 为主，那么 $Q$ 中每一个点都可以和这个 $P$ 中每一个点相交，$P$ 中点的数量就是这个 $\text{Area}(P)$，那么 $Q$ 中一共有 $\text{Area}(Q)$ 个点，总的积分就是 $\text{Area}(P)\times\text{Area}(Q)$。

2. 分母分析 ($|D|$)

集合 $D$ 表示所有能让 $P$ 和 $Q$ 接触或重叠的平移向量 $\mathbf{t}$。这个集合实际上就是 $P$ 和 $-Q$（$Q$ 关于原点的中心对称图形）的闵可夫斯基和：

$$D = P \oplus (-Q)$$

由于 $P$ 和 $Q$ 都是凸多边形，它们的闵可夫斯基和 $D$ 也是一个凸多边形。

构建 $D$ 的方法：

凸多边形的闵可夫斯基和可以通过将两个多边形的所有边向量收集起来，按照极角排序，然后首尾相连构成一个新的多边形。

• $P$ 的边向量：$P_{i+1} - P_i$。

• $-Q$ 的边向量：$-Q$ 的边相当于 $Q$ 的边的反向。即如果 $Q$ 的边是 $Q_{j+1} - Q_j$，那么对应的 $-Q$ 的边向量就是 $Q_j - Q_{j+1}$。

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<Point> poly1(N), poly2(M);
    for (int i = 0; i < N; ++i) {
        cin >> poly1[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> poly2[i];
        poly2[i]=-poly2[i];
    }
    auto poly_res = minkowski(poly1, poly2);
    DB ans = polygonArea(poly1) * polygonArea(poly2) / polygonArea(poly_res);
    cout << fsp(12) << ans << "\n";
}

AC代码

AC
https://codeforces.com/gym/106252/submission/361314647

源代码

/**
 * Problem: G. Collision Damage
 * Contest: The 2025 ICPC Asia Shenyang Regional Contest (The 4th Universal Cup. Stage 6: Grand Prix of Shenyang)
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106252/problem/G
 * Created: 2026-02-03 21:27:50
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

/*2026-2-3 增加编译器识别 Real 类型的功能，以使用不同类型的这个实现
 *
 */
using Real = ll;

int sgn(auto x) {
    if (-eps < x && x < eps) return 0;
    return x < 0 ? -1 : 1;
}

struct Point {
    Real x, y;

    explicit Point(Real x_ = 0, Real y_ = 0) : x(x_), y(y_) {
    }

    // 只对左值生效的复合运算符
    Point &operator+=(Point p) & {
        x += p.x, y += p.y;
        return *this;
    }

    Point &operator-=(Point p) & {
        x -= p.x, y -= p.y;
        return *this;
    }

    Point &operator*=(Real t) & {
        x *= t, y *= t;
        return *this;
    }

    Point &operator/=(Real t) & {
        x /= t, y /= t;
        return *this;
    }

    Point operator-() const { return Point(-x, -y); }

    friend Point operator+(Point a, Point b) { return a += b; }
    friend Point operator-(Point a, Point b) { return a -= b; }
    friend Point operator*(Point a, Real b) { return a *= b; }
    friend Point operator*(Real a, Point b) { return b *= a; }
    friend Point operator/(Point a, Real b) { return a /= b; }

    friend bool operator<(Point a, Point b) {
        int sx = sgn(a.x - b.x);
        if (sx != 0) return a.x < b.x;
        return a.y < b.y;
    }

    friend bool operator>(Point a, Point b) { return b < a; }

    friend bool operator==(Point a, Point b) {
        return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;
    }

    friend bool operator!=(Point a, Point b) { return !(a == b); }

    friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
    // friend ostream &operator<<(ostream &os, Point p) { return os << "(" << p.x << ", " << p.y << ")"; }

    auto norm() const {
        if constexpr (is_integral_v<Real>) {
            return (__int128_t) x * x + (__int128_t) y * y;
        } else {
            return x * x + y * y;
        }
    }

    DB abs() const { return sqrt((long double) norm()); }
};

using Vector = Point;

auto cross(Point a, Point b) {
    // 在 Real 为整数的时候，使用 __int128_t 整型进行计算
    if constexpr (is_integral_v<Real>) {
        return (__int128_t) a.x * b.y - (__int128_t) a.y * b.x;
    } else {
        return a.x * b.y - a.y * b.x;
    }
}

// Real cross(Point p1, Point p2, Point p0) { // 叉乘 (p1 - p0) x (p2 - p0);
//     return cross(p1 - p0, p2 - p0);
// }
auto dot(Point a, Point b) {
    // 在 Real 为整数的时候，使用 __int128_t 整型进行计算
    if constexpr (is_integral_v<Real>) {
        return (__int128_t) a.x * b.x + (__int128_t) a.y * b.y;
    } else {
        return a.x * b.x + a.y * b.y;
    }
}

// 采用两点式
struct Line {
    Point p1, p2;

    Line() {
    }

    Line(Point a, Point b) : p1(a), p2(b) {
    }

    friend bool operator<(Line a, Line b) {
        if (a.p1 != b.p1) return a.p1 < b.p1;
        return a.p2 < b.p2;
    }

    friend bool operator==(Line a, Line b) {
        if (a.p1 != b.p1) return false;
        if (a.p2 != b.p2) return false;
        return true;
    }

    friend istream &operator>>(istream &is, Line &e) {
        Real a, b, c, d;
        is >> a >> b >> c >> d;
        e = Line(Point(a, b), Point(c, d));
        return is;
    }

    // friend ostream&operator<<(ostream &os, Line l) {
    //     return os << "<" << l.p << ", " << l.q << ">";
    // }
};

// 使用这个东西，Point 必须是 double 等小数类型
Point project(Point p, Line l) {
    Point vec = l.p2 - l.p1;
    //                        这个距离反正早除晚除都要除掉
    DB r = dot(vec, p - l.p1) / ((DB) vec.x * vec.x + vec.y * vec.y);
    return l.p1 + vec * r;
}

Point reflect(Point p, Line l) {
    Point proj = project(p, l);
    return proj + proj - p;
}

mt19937 rng(233);

#define ON_SEGMENT 0
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE (-1)
#define ONLINE_BACK 2
#define ONLINE_FRONT (-2)

int CCW(Point p, Line l) {
    Vector a = l.p2 - l.p1, b = p - l.p1;
    if (sgn(cross(a, b)) > 0) {
        return COUNTER_CLOCKWISE;
    }
    if (sgn(cross(a, b)) < 0) {
        return CLOCKWISE;
    }
    if (sgn(dot(a, b)) < 0) {
        return ONLINE_BACK;
    }
    if (a.norm() < b.norm()) return ONLINE_FRONT;
    return ON_SEGMENT;
}

bool isOrthogonal(Line a, Line b) {
    Vector c = a.p2 - a.p1, d = b.p2 - b.p1;
    return !sgn(dot(c, d));
}

bool isParallel(Line a, Line b) {
    Vector c = a.p2 - a.p1, d = b.p2 - b.p1;
    return !sgn(cross(c, d));
}

bool isIntersect(Line a, Line b) {
    // 判断线段相交
    return CCW(b.p1, a) * CCW(b.p2, a) <= 0 && CCW(a.p1, b) * CCW(a.p2, b) <= 0;
}

// bool isIntersectStrict(Line a,Line b){    // 判断线段相交
//     return CCW(b.p1,a)*CCW(b.p2,a)<0 && CCW(a.p1,b)*CCW(a.p2,b)<0;
// }
// p+tv=q+sw
// (p-q) x w+tv x w = 0     (利用叉乘乘以自身为0，消掉sw)
// t=-(p-q)x w/(vxw)
// 传入的是方向式  拿到的是两直线交点
Point getintersect(const Line &a, const Line &b) {
    Point p = a.p1, v = a.p2 - a.p1, q = b.p1, w = b.p2 - b.p1;
    Point u = p - q;
    DB t = cross(w, u) / cross(v, w);
    return p + v * t;
}

// 也可以用 project 来算
DB distancePL(Point p, Line l) {
    auto val = cross(l.p2 - l.p1, p - l.p1);
    return sgn(val) * val / (l.p2 - l.p1).abs();
}

// AC https://qoj.ac/submission/2001668
DB distancePS(Point p, Line l) {
    // 避免 distanceSS 调用的时候发生这个退化（即线段退化为了点）
    if (l.p1 == l.p2) {
        return (p - l.p1).abs();
    }
    Vector t = l.p2 - l.p1;
    if (sgn(dot(t, p - l.p1)) < 0) {
        return (p - l.p1).abs();
    }
    if (sgn(dot(t, p - l.p2)) > 0) {
        return (p - l.p2).abs();
    }
    return distancePL(p, l);
}

// AC https://qoj.ac/submission/2001588
DB distanceSS(Line a, Line b) {
    if (isIntersect(a, b)) return 0;
    return min({distancePS(a.p1, b), distancePS(a.p2, b), distancePS(b.p1, a), distancePS(b.p2, a)});
}

DB polygonArea(const vector<Point> &poly) {
    DB res = 0;
    for (int i = 0; i < poly.size(); ++i) {
        res += cross(poly[i], poly[(i + 1) % SZ(poly)]);
    }
    res = abs(res)/2.0;
    return res;
}

void reorder_polygon(vector<Point> &poly) {
    ll n = poly.size();
    Point p1 = poly[1] - poly[0], p2 = poly[2] - poly[0];
    if (sgn(cross(p1, p2)) <= 0) {
        reverse(poly.begin(), poly.end());
    }
    // 找到字典序最小的点
    ll pos_mn = 0;
    for (int i = 1; i < n; ++i) {
        if (poly[i] < poly[pos_mn]) {
            pos_mn = i;
        }
    }
    // Performs a left rotation on a range of elements
    // 向左循环移动，把 pos_mn 移动到第一个 [0]
    rotate(poly.begin(), poly.begin() + pos_mn, poly.end());
}

// 不允许自交的多边形，顺序都可以，会把 poly 变为 CCW 顺序（逆时针）
// AC https://qoj.ac/submission/2002121
bool isConvex(vector<Point> &poly) {
    ll n = poly.size();
    reorder_polygon(poly);
    // 在一个标准的凸多边形中，如果我们站在最左下角的点（poly[0]）往外看
    // 其他所有顶点 poly[1], poly[2], ..., poly[n-1] 应该按照逆时针方向整齐排列。
    // 从而排除星形（自交）多边形和乱序点集。
    for (int i = 1; i < n - 1; ++i) {
        if (sgn(cross(poly[i] - poly[0], poly[i + 1] - poly[0])) <= 0) {
            return false;
        }
    }
    // 判断单个内角是否 ≥ 180。
    for (int i = 0; i < n; ++i) {
        ll i1 = (i + 1) % n, i2 = (i + 2) % n;
        Vector a = poly[i1] - poly[i], b = poly[i2] - poly[i1];
        // 加上大于等于，就相当于排除所有的退化情况，不允许内角为 180 度
        if (sgn(cross(a, b)) <= 0) {
            return false;
        }
    }
    return true;
}

// 2 是包含，1是在线上，0是出界
int isInPolygon(Point p, const vector<Point> &poly) {
    ll res = 0;
    Line l(p, p + Point(2e5, rng()));
    for (int i = 0; i < poly.size(); ++i) {
        int i1 = (i + 1) % SZ(poly);
        Line seg = Line(poly[i], poly[i1]);
        int ccw = CCW(p, seg);
        if (ccw == ON_SEGMENT) {
            return 1;
        }
        if (isIntersect(l, seg)) {
            ++res;
        }
    }
    // 奇偶法则，多边形内点的射线一定只会经过奇数条边。
    if (res & 1) return 2;
    return 0;
}

// 定义获取区域的辅助函数，辅助
int get_part_of_point(const Point &p) {
    if (p.y < 0) return 0; // 下半平面 (-pi, 0)
    if (p.y == 0 && p.x >= 0) return 1; // 角度为 0 的部分 (含原点)
    return 2; // 上半平面 (0, pi]
}

// 你需要将所有点按照 atan2(yi,xi)进行排序，也即从 x 轴负半轴（不含）开始进行逆时针排序。
// AC https://qoj.ac/submission/2001485
void polar_angle_sort(vector<Point> &poly) {
    sort(poly.begin(), poly.end(), [](const Point &a, const Point &b)-> bool {
        int part1 = get_part_of_point(a), part2 = get_part_of_point(b);
        if (part1 != part2) {
            return part1 < part2;
        }
        return sgn(cross(a, b)) == 1;
    });
}

// 两个小凸包，合成一个大凸包，这个大凸包，即闵可夫斯基和
// 参考了 https://github.com/hh2048/XCPC 的 mincowski
// minkowski 的减法就是加上关于原点的中心对称图形
// AC https://qoj.ac/submission/2002545
vector<Point> minkowski(vector<Point> &P1, vector<Point> &P2) {
    reorder_polygon(P1);
    reorder_polygon(P2);
    int n = P1.size(), m = P2.size();
    vector<Point> V1(n), V2(m);
    // 预处理：计算差分向量（边向量）
    for (int i = 0; i < n; i++) {
        V1[i] = P1[(i + 1) % n] - P1[i];
    }
    for (int i = 0; i < m; i++) {
        V2[i] = P2[(i + 1) % m] - P2[i];
    }
    vector<Point> ans = {P1.front() + P2.front()};
    int t = 0, i = 0, j = 0;
    while (i < n && j < m) {
        // cross(V1,V2)> 0，就说明 V1 小于这个 V2(在 CCW 下)
        // 所以先选择这个小的 V1，反之同理
        Point val = sgn(cross(V1[i], V2[j])) > 0 ? V1[i++] : V2[j++];
        ans.push_back(ans.back() + val);
    }
    // 处理剩余的边
    while (i < n) ans.push_back(ans.back() + V1[i++]);
    while (j < m) ans.push_back(ans.back() + V2[j++]);
    return ans;
}

void Solve() {
    ll N, M;
    cin >> N >> M;
    vector<Point> poly1(N), poly2(M);
    for (int i = 0; i < N; ++i) {
        cin >> poly1[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> poly2[i];
        poly2[i]=-poly2[i];
    }
    auto poly_res = minkowski(poly1, poly2);
    DB ans = polygonArea(poly1) * polygonArea(poly2) / polygonArea(poly_res);
    cout << fsp(12) << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106252/submission/361314647

*/

心路历程（WA，TLE，MLE……）