Znzryb's Blog

80. Convex Checker

Posted on 2026-02-03 Edited on 2026-02-19

题目大意

思路讲解

原先的凸性检测没法检测出这样子的五角星。

// 不允许自交的多边形，顺序都可以，会把 poly 变为 CCW 顺序（逆时针）
// AC https://qoj.ac/submission/2002121
bool isConvex(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[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;
}

AC代码

AC
https://qoj.ac/submission/2002045

AC https://qoj.ac/submission/2002100

AC https://qoj.ac/submission/2002121

源代码

/**
 * Problem: Convex Checker
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-7730
 * Created: 2026-02-03 18:38:37
 * 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;
    ll idx;

    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)]) / 2;
    }
    res = abs(res);
    return res;
}

// 不允许自交的多边形，顺序都可以，会把 poly 变为 CCW 顺序（逆时针）
// AC https://qoj.ac/submission/2002121
bool isConvex(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[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;
    });
}

void Solve() {
    ll N;
    cin >> N;
    vector<Point> poly(N);
    for (int i = 0; i < N; ++i) {
        cin >> poly[i];
    }
    // polar_angle_sort(poly);
    if (isConvex(poly)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

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

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

/*
AC
https://qoj.ac/submission/2002045

*/

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

81. 极角排序

Posted on 2026-02-03 Edited on 2026-02-19

题目大意

思路讲解

AC代码

AC
https://qoj.ac/submission/2001485

源代码

/**
 * Problem: 极角排序
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-10259
 * Created: 2026-02-03 12:49:30
 * 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;
    ll idx;

    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 << ")"; }

    Real norm() const { return x * x + y * y; }
    DB abs() const { return sqrt(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)
// 传入的是方向式  拿到的是两直线交点
// Real 必须设为 DB
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();
}
DB distancePS(Point p,Line l){
    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);
}
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)])/2;
    }
    res=abs(res);
    return res;
}
// 要求给出的点按照逆时针方向给出
bool isConvex(const vector<Point> &poly){
    for (int i=0;i<poly.size();++i){
        ll i1=(i+1)%SZ(poly),i2=(i+2)%SZ(poly);
        Vector a=poly[i]-poly[i1],b=poly[i2]-poly[i1];
        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;
    });
}

void Solve() {
    ll N;
    cin >> N;
    vector<Point> poly(N);
    for (int i=0;i<N;++i) {
        cin>>poly[i];
        poly[i].idx=i+1;
    }
    polar_angle_sort(poly);
    for (int i=0;i<N;++i) {
        cout<<poly[i].idx<<" ";
    }
}

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

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

/*
AC
https://qoj.ac/submission/2001485

*/

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

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

Posted on 2026-02-03 Edited on 2026-03-07

题目大意

在一个基于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$ 移动到所有可能的位置时，总共有多少次“像素重叠”发生？

让我们换个角度思考：

取 $Q$ 中的任意一个特定像素点 $q_0$ 。
当 $Q$ 在平面上到处移动时，这个点 $q_0$ 会经过平面的每一个位置。
它什么时候会和 $P$ 发生“重叠”？也就是当 $q_0$ 落在 $P$ 内部的时候。
因为 $P$ 有 $N$ 个像素，所以 $q_0$ 会在 $N$ 个不同的位置（平移向量）上为“总重叠面积”贡献 1 个单位。
现在，对 $Q$ 中的每一个像素点都重复这个过程。 $Q$ 总共有 $M$ 个像素点。
因此，总的重叠贡献 = ( $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……）

2025-沈阳站-区域赛-F. The Bond Beyond Time（友谊天长地久）（如何使用 bfs 找一个无弦环）（这种题目，我感觉啊，想要做出来的话，要么就是你的思路得比较好，要么就是还是得写个对拍）

Posted on 2026-02-02 Edited on 2026-02-23

题目大意

"
Sulfox the fennec fox已经建立了一个迷宫，并邀请他的两个朋友Alice和Bob来尝试。迷宫可以抽象为一个简单的、连通的无向图，其中有 $n$ 个顶点和 $m$ 条边，Alice和Bob在两个指定的不同顶点开始。

在任何玩家移动之前，Sulfox必须为每条无向边选择一个方向，将迷宫变成一个有向图。然后，为了找到对方，两位玩家在定向迷宫内进行回合移动。在每一轮中，他们同时独立行动，不留下任何标记或沟通；相反，他们采取“最愚蠢”的策略：

如果玩家当前位于一个具有一个或多个出边的顶点，则他们会任意穿越一个出边到相邻顶点；
否则，如果他们当前的顶点没有出边，则他们将停留在该顶点。

作为对自己迷宫设计技能感到自豪的Sulfox，希望将通道定向，以便Alice和Bob永远不会相遇。鉴于无向图和Alice和Bob的起始顶点，请帮助Sulfox定向每条边，使得无论Alice和Bob如何在每一轮中做出选择，他们永远不会在任何一轮结束时占据同一顶点。如果不存在这样的定向，请报告。"

思路讲解

我记得是这样子的，只要两个玩家所在顶点不直接相连，就简单了，所有连着两个点的边全部指向这两点，可以把这两个玩家封死。

两个玩家所在顶点直接相连，就找最小的环，所有其他点（边）指向这个环，避免两个玩家离开这个环。

我们需要两次 bfs 实现：

这一部分 bfs 实现，负责这个找到包含 $X → Y$ 的环（这个相对容易），如果知道到了，直接输出答案即可。

for (int i=1;i<=1;++i) {
    g[X].erase(find(all(g[X]),Y));
    g[Y].erase(find(all(g[Y]),X));
    queue<ll> q;
    vector<char> vis(N + 2);
    vis[X] = true;
    q.push(X);
    vector<ll> parent(N + 2);
    while (!q.empty()) {
        auto u=q.front();
        q.pop();
        if (vis[Y]) {
            break;
        }
        for (auto to:g[u]) {
            if (vis[to]) continue;
            vis[to]=true;
            parent[to]=u;
            q.push(to);
        }
    }
    if (!vis[Y]) {
        break;
    }
    cout<<"Yes\n";
    vector<ll> cycle_ls;
    for (ll node=Y;node!=X;node=parent[node]) {
        edge_ls.erase(lower_bound(all(edge_ls),
            pair{min(node,parent[node]),max(node,parent[node])}));
        cycle_ls.push_back(node);
        cout<<parent[node]<<" "<<node<<"\n";
    }
    {
        edge_ls.erase(lower_bound(all(edge_ls),
            pair{X,Y}));
        cycle_ls.push_back(X);
        cout<<Y<<" "<<X<<"\n";
    }
    sort(all(cycle_ls));
    for (auto [u,v]:edge_ls) {
        if (binary_search(all(cycle_ls),u) ) {
            cout<<v<<" "<<u<<"\n";
        }else if (binary_search(all(cycle_ls),v)){
            cout<<u<<" "<<v<<"\n";
        }else {
            cout<<u<<" "<<v<<"\n";
        }
    }
    return;
}

如果没有包含 $X\to Y$ 的这个环，就从 $X$ 出发，随便找一个这个无弦环即可。

为什么需要这两个部分呢？

只要我们在第一阶段排除这样子的包含 $X\to Y$ 的这个环，我们找到的环上的点的边就不会和 $Y$ 相连。（可以避免出现一些奇奇怪怪的情况）

if (isout==false){
    g[X].push_back(Y);
    g[Y].push_back(X);
    // 没有边权，可以直接使用bfs得到最小环。
    queue<ll> q;
    vector<char> vis(N + 2);
    vis[X] = true;
    q.push(X);
    vector<ll> parent(N + 2);
    // 我们找的环，不仅可以包含这个 X - Y 这条边，也可以不包含 X-Y 这条边
    // 只要把 X，Y 诱导的我们的环上即可
    ll st_ed_cycle = 0, another_pa_st_ed = 0;
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        if (st_ed_cycle != 0) {
            break;
        }
        for (auto to: g[u]) {
          // 排除 parent 点
            if (to == parent[u]) continue;
            // 一旦只要不是 parent 点就遍历到了，那就是遇到环了
            if (vis[to]) {
                another_pa_st_ed = u;
                st_ed_cycle = to;
                continue;
            }
            vis[to] = true;
            parent[to] = u;
            q.push(to);
        }
    }
    // 一个环都没有找到？说明图本身是一颗树
    if (st_ed_cycle == 0) {
        cout << "No\n";
        return;
    }
    vector<ll> order_of_cycle,another_part_of_cycle;
    vector<char>  vis_route(N+2);
    // bfs 还原路径，比较难的地方就是环被砍成了了两半
    // 第一段路径，使用这个 parent 还原
    for (ll i=st_ed_cycle;i!=X;i=parent[i]) {
        order_of_cycle.push_back(i);
        vis_route[i]=true;
    }
    vis_route[X]=true;
    order_of_cycle.push_back(X);
    ll overlap_node=0;
    // 第二段路径还原
    for (ll i=another_pa_st_ed;overlap_node=i,!vis_route[i];i=parent[i]) {
        vis_route[i]=true;
        another_part_of_cycle.push_back(i);
    }
    reverse(all(order_of_cycle));
    order_of_cycle.insert(order_of_cycle.end(),all(another_part_of_cycle));
    order_of_cycle.push_back(overlap_node);
    // order_of_cycle.insert(find(all(order_of_cycle),overlap_node)+1 , order_of_cycle.front());
    // 接下来生成这个序列
    vector<pair<ll,ll>> out_ls;
    for (int i=0;i<SZ(order_of_cycle)-1;++i) {
        ll u=order_of_cycle[i],v=order_of_cycle[i+1];
        edge_ls.erase(lower_bound(all(edge_ls),
            pair{min(u, v), max(u, v)}));
        // cout<<u<<" "<<v<<"\n";
        out_ls.emplace_back(u,v);
    }
    if (!vis_route[Y] ) {
        edge_ls.erase(lower_bound(all(edge_ls),
           pair{X, Y }));
        vis_route[Y]=true;
        // cout<<Y<<" "<<X<<"\n";
        out_ls.emplace_back(Y,X);
    }
    // for (ll u=overlap_node,v=order_of_cycle.front();false;) {
    //     edge_ls.erase(lower_bound(all(edge_ls),
    //         pair{min(u, v), max(u, v)}));
    //     // cout<<u<<" "<<v<<"\n";
    //     out_ls.emplace_back(u,v);
    // }
    for (auto [u,v]:edge_ls) {
        if (vis_route[u] ) {
            // cout<<v<<" "<<u<<"\n";
            out_ls.emplace_back(v,u);
        }else if (vis_route[v]){
            // cout<<u<<" "<<v<<"\n";
            out_ls.emplace_back(u,v);
        }else {
            // cout<<u<<" "<<v<<"\n";
            out_ls.emplace_back(u,v);
        }
    }
    cout<<"Yes\n";
    for (auto [u,v]:out_ls) {
        cout<<u<<" "<<v<<"\n";
    }
}

AC代码

AC
https://qoj.ac/submission/2005037

源代码

/**
 * Problem: The Bond Beyond Time
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-14945
 * Created: 2026-02-04 14:54:31
 * 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 LD = long 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,testcase;

/*
 *
 */

void Solve() {
    ll N, M, X, Y;
    cin >> N >> M >> X >> Y;
    // if (testcase==23) {
    //     cerr<<N<<" "<<M<<" "<<X<<" "<<Y<<"\n";
    // }
    tie(X, Y) = pair<ll, ll>{min(X, Y), max(X, Y)};
    vector<vector<ll> > g(N + 2);
    vector<pair<ll, ll> > edge_ls;
    for (int i = 1; i <= M; ++i) {
        ll u, v;
        cin >> u >> v;
        // if (testcase==23) {
        //     cerr<<u<<" "<<v<<"\n";
        // }
        g[u].push_back(v);
        g[v].push_back(u);
        edge_ls.emplace_back(min(u, v), max(u, v));
    }
    sort(all(edge_ls));
    if (binary_search(all(edge_ls), pair<ll, ll>{X, Y})) {
        bool isout=false;
        for (int i=1;i<=1;++i) {
            g[X].erase(find(all(g[X]),Y));
            g[Y].erase(find(all(g[Y]),X));
            queue<ll> q;
            vector<char> vis(N + 2);
            vis[X] = true;
            q.push(X);
            vector<ll> parent(N + 2);
            while (!q.empty()) {
                auto u=q.front();
                q.pop();
                if (vis[Y]) {
                    break;
                }
                for (auto to:g[u]) {
                    if (vis[to]) continue;
                    vis[to]=true;
                    parent[to]=u;
                    q.push(to);
                }
            }
            if (!vis[Y]) {
                break;
            }
            cout<<"Yes\n";
            vector<ll> cycle_ls;
            for (ll node=Y;node!=X;node=parent[node]) {
                edge_ls.erase(lower_bound(all(edge_ls),
                    pair{min(node,parent[node]),max(node,parent[node])}));
                cycle_ls.push_back(node);
                cout<<parent[node]<<" "<<node<<"\n";
            }
            {
                edge_ls.erase(lower_bound(all(edge_ls),
                    pair{X,Y}));
                cycle_ls.push_back(X);
                cout<<Y<<" "<<X<<"\n";
            }
            sort(all(cycle_ls));
            for (auto [u,v]:edge_ls) {
                if (binary_search(all(cycle_ls),u) ) {
                    cout<<v<<" "<<u<<"\n";
                }else if (binary_search(all(cycle_ls),v)){
                    cout<<u<<" "<<v<<"\n";
                }else {
                    cout<<u<<" "<<v<<"\n";
                }
            }
            return;
        }
        // cout<<"No\n";
        // return;
        if (isout==false){
            g[X].push_back(Y);
            g[Y].push_back(X);
            // 没有边权，可以直接使用bfs得到最小环。
            queue<ll> q;
            vector<char> vis(N + 2);
            vis[X] = true;
            q.push(X);
            vector<ll> parent(N + 2);
            // 我们找的环，不仅可以包含这个 X - Y 这条边，也可以不包含 X-Y 这条边
            // 只要把 X，Y 诱导的我们的环上即可
            ll st_ed_cycle = 0, another_pa_st_ed = 0;
            while (!q.empty()) {
                auto u = q.front();
                q.pop();
                if (st_ed_cycle != 0) {
                    break;
                }
                for (auto to: g[u]) {
                    if (to == parent[u]) continue;
                    if (vis[to]) {
                        another_pa_st_ed = u;
                        st_ed_cycle = to;
                        continue;
                    }
                    vis[to] = true;
                    parent[to] = u;
                    q.push(to);
                }
            }
            // 一个环都没有找到？说明图本身是一颗树
            if (st_ed_cycle == 0) {
                cout << "No\n";
                return;
            }
            vector<ll> order_of_cycle,another_part_of_cycle;
            vector<char>  vis_route(N+2);
            for (ll i=st_ed_cycle;i!=X;i=parent[i]) {
                order_of_cycle.push_back(i);
                vis_route[i]=true;
            }
            vis_route[X]=true;
            order_of_cycle.push_back(X);
            ll overlap_node=0;
            for (ll i=another_pa_st_ed;overlap_node=i,!vis_route[i];i=parent[i]) {
                vis_route[i]=true;
                another_part_of_cycle.push_back(i);
            }
            reverse(all(order_of_cycle));
            order_of_cycle.insert(order_of_cycle.end(),all(another_part_of_cycle));
            order_of_cycle.push_back(overlap_node);
            // order_of_cycle.insert(find(all(order_of_cycle),overlap_node)+1 , order_of_cycle.front());
            // 接下来生成这个序列
            vector<pair<ll,ll>> out_ls;
            for (int i=0;i<SZ(order_of_cycle)-1;++i) {
                ll u=order_of_cycle[i],v=order_of_cycle[i+1];
                edge_ls.erase(lower_bound(all(edge_ls),
                    pair{min(u, v), max(u, v)}));
                // cout<<u<<" "<<v<<"\n";
                out_ls.emplace_back(u,v);
            }
            if (!vis_route[Y] ) {
                edge_ls.erase(lower_bound(all(edge_ls),
                   pair{X, Y }));
                vis_route[Y]=true;
                // cout<<Y<<" "<<X<<"\n";
                out_ls.emplace_back(Y,X);
            }
            // for (ll u=overlap_node,v=order_of_cycle.front();false;) {
            //     edge_ls.erase(lower_bound(all(edge_ls),
            //         pair{min(u, v), max(u, v)}));
            //     // cout<<u<<" "<<v<<"\n";
            //     out_ls.emplace_back(u,v);
            // }
            for (auto [u,v]:edge_ls) {
                if (vis_route[u] ) {
                    // cout<<v<<" "<<u<<"\n";
                    out_ls.emplace_back(v,u);
                }else if (vis_route[v]){
                    // cout<<u<<" "<<v<<"\n";
                    out_ls.emplace_back(u,v);
                }else {
                    // cout<<u<<" "<<v<<"\n";
                    out_ls.emplace_back(u,v);
                }
            }
            cout<<"Yes\n";
            for (auto [u,v]:out_ls) {
                cout<<u<<" "<<v<<"\n";
            }
        }

    } else {
        cout << "Yes\n";
        for (auto [u,v]: edge_ls) {
            if (u == X || u == Y) {
                cout << v << " " << u << "\n";
            } else if (v == X || v == Y) {
                cout << u << " " << v << "\n";
            } else {
                cout << v << " " << u << "\n";
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2005037

*/

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

这道题目的 SPJ 怎么写？

编写这道题 SPJ（Special Judge）的核心难点在于：如何验证“无论怎么走都遇不到”这一条件。

因为题目中描述的移动策略是“任意选择一条出边（arbitrarily traverse）”，这意味着玩家的移动是不确定的。你不能只模拟一条路径，而是必须模拟所有可能的路径。

核心思路：集合模拟（Set Simulation）

要在 SPJ 中解决这个问题，关键点不是记录 Alice 和 Bob “在哪一个点”，而是记录他们当前可能在哪些点的集合。

由于 $N \le 300$ ，我们可以使用 C++ 的 std::bitset<305> 来高效地维护这个集合。

SPJ 的具体实现步骤

1. 基础校验 (Basic Validation)

首先，必须确保选手输出的图是合法的：

边数对应：选手输出的有向边必须和输入的无向边一一对应（通过 multiset 或排序后比对）。
点范围：点的编号在 $1 \dots N$ 之间。

2. 状态定义 (The Critical Point)

这是 SPJ 最关键的部分。

设 $S_A^{(t)}$ 为第 $t$ 轮结束时，Alice 可能所在的所有顶点的集合。
设 $S_B^{(t)}$ 为第 $t$ 轮结束时，Bob 可能所在的所有顶点的集合。

初始状态：

$S_A^{(0)} = \{Alice_{start}\}, \quad S_B^{(0)} = \{Bob_{start}\}$

3. 状态转移 (Transition)

每一轮模拟时，我们需要计算下一轮的集合 $S^{(t+1)}$ 。规则如下：

对于集合中的每一个点 $u \in S^{(t)}$ ：

情况 A（有出边）：如果 $u$ 有出边指向 $v_1, v_2, \dots$ ，那么在下一轮，Alice/Bob 可能会出现在这些邻居中的任何一个。将 $\{v_1, v_2, \dots\}$ 全部加入 $S^{(t+1)}$ 。
情况 B（无出边）：如果 $u$ 没有出边，根据题目规则，玩家停留在原地。将 $u$ 加入 $S^{(t+1)}$ 。

用位运算表示非常快：

next_mask = 0;
for (int u = 1; u <= n; u++) {
    if (current_mask.test(u)) { // 如果当前可能在 u
        if (adj[u].none()) {    // u 没有出边
            next_mask.set(u);   // 下一轮还在 u
        } else {                // u 有出边
            next_mask |= adj[u]; // 下一轮可能在 u 的所有邻居
        }
    }
}

4. 碰撞检测 (Collision Check)

在任何时刻 $t$ ，如果 Alice 和 Bob 的可能位置集合有交集，说明存在一种走法让他们相遇，判为 WA。

判定条件：(S_A & S_B).any() == true

5. 终止条件 (Termination)

模拟不能无限进行下去。我们有两个终止条件：

相遇：检测到交集，直接 quitf(_wa, ...)****。
**死循环（安全）：**如果当前的“状态对” $(S_A, S_B)$ 曾经出现过，说明我们进入了一个循环，而且在这个循环中没有发生碰撞。那么继续跑下去也不会碰撞。此时判为 AC。

使用 set<pair<string, string>> history 记录 bitset 的状态。

完整的 SPJ 代码结构 (基于 testlib.h)

这是一个标准的写法，你可以直接参考：

#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);

    int t = inf.readInt(); // 读取测试用例数
    while (t--) {
        int n = inf.readInt();
        int m = inf.readInt();
        int startA = inf.readInt();
        int startB = inf.readInt();

        // 1. 读取标准输入的边 (用于校验)
        multiset<pair<int, int>> edges;
        for (int i = 0; i < m; i++) {
            int u = inf.readInt();
            int v = inf.readInt();
            if (u > v) swap(u, v);
            edges.insert({u, v});
        }

        string ja = ans.readToken(); // Jury's answer
        string pa = ouf.readToken(); // Participant's answer

        if (ja != pa) {
            quitf(_wa, "Answer mismatch! Expected %s, found %s", ja.c_str(), pa.c_str());
        }

        if (pa == "No") continue; // 如果是 No，且 Jury 也是 No，这组过了

        // 2. 建图 & 校验选手输出的边
        vector<bitset<MAXN>> adj(n + 1);
        vector<bool> has_outgoing(n + 1, false);

        for (int i = 0; i < m; i++) {
            int u = ouf.readInt();
            int v = ouf.readInt();
            
            // 校验边是否存在于原图中
            int u_chk = u, v_chk = v;
            if (u_chk > v_chk) swap(u_chk, v_chk);
            auto it = edges.find({u_chk, v_chk});
            if (it == edges.end()) {
                quitf(_wa, "Edge %d->%d invalid or used twice", u, v);
            }
            edges.erase(it);

            // 建图
            adj[u].set(v);
            has_outgoing[u] = true;
        }

        // 3. 核心模拟逻辑
        bitset<MAXN> curA, curB;
        curA.set(startA);
        curB.set(startB);

        // 状态记忆化，防止死循环超时
        set<pair<string, string>> visited_states; 
        
        bool ok = true;
        int steps = 0;
        
        // 这里的 20000 是一个保险值，实际上如果有环，visited_states 会更早截断
        while (steps++ < 20000) {
            // Check Collision
            if ((curA & curB).any()) {
                quitf(_wa, "Alice and Bob meet at step %d", steps);
            }

            // Check Cycle (Memoization)
            string sa = curA.to_string();
            string sb = curB.to_string();
            if (visited_states.count({sa, sb})) {
                // 状态重复，且之前没遇到 WA，说明进入安全循环
                break; 
            }
            visited_states.insert({sa, sb});

            // Move Alice
            bitset<MAXN> nextA;
            for (int i = 1; i <= n; i++) {
                if (curA[i]) {
                    if (!has_outgoing[i]) nextA.set(i); // Stay
                    else nextA |= adj[i];               // Move
                }
            }

            // Move Bob
            bitset<MAXN> nextB;
            for (int i = 1; i <= n; i++) {
                if (curB[i]) {
                    if (!has_outgoing[i]) nextB.set(i); // Stay
                    else nextB |= adj[i];               // Move
                }
            }

            curA = nextA;
            curB = nextB;
        }
    }

    quitf(_ok, "All test cases passed!");
}

总结

这道题 SPJ 的精髓在于不要去想“他们走了哪条路”，而是利用 $N$ 较小的特点，并行追踪“他们可能在的所有位置”。只要这两个位置集合永远不相交，选手的答案就是正确的。

2025-ICPC-Asia-Taiwan-Online-台湾网络赛-J. Gas Station（贪心的关键是，找到最优子结构）（最优子结构是什么？就是在不在这贪取决于什么！）（每一颗子树都最小化加油站数量，再检测在最小化加油站数量前提下，是否违反了限制，强迫摆放加油站）

Posted on 2026-02-02 Edited on 2026-02-19

题目大意

亚历克斯正在规划在一个简化的台湾高速公路系统模型上设立休息区。该系统包含 $n$ 个互通立交，由 $n-1$ 条双向道路连接。网络是连通的，任意一对互通立交之间有且仅有一条最短路径。第 $i$ 条道路连接互通 $u_i$ 和 $v_i$ ，长度为 $l_i$ 。

可以建造恰好 $k$ 个带加油站的休息区，每个位于一个互通。司机可以从任意互通开始旅行到任何其他互通，始终沿着唯一最短路径。他们每次旅行都会带满油箱，只能在设有休息区的互通处加油。

亚历克斯想知道可能的最小燃油箱容量 $d$ ，以便可以以一种方式放置这 $k$ 个休息区，确保没有任何司机会耗尽燃油。在任何旅行中，司机永远不应该在沿途行驶超过 $d$ 个单位而不经过休息区，包括旅程的开始或结束。目标是找出最小的 $d$ ，假设休息区被以最佳方式放置。

思路讲解

https://hackmd.io/@tmt514/Bk_lRqjill#Problem-J—Gas-Station

官方题解

Problem J - Gas Station

觀察到如果選擇了一個比正確答案還要小的 $d'$ ，則需要的加油站數量會大於 $k$ ，反之小於等於 $k$ 。因此藉由二分搜尋法，透過指定的 $d'$ 計算所需要的加油站數量，來檢驗選定的 $d'$ 是太大或是太小。
對於計算加油站數量的部分，由於我們固定了 $d'$ ，因此可以簡單的使用 DFS 來計算。設 $\mathsf{dfs}(r)$ 為以 $r$ 為根的子樹， $r$ 到最近的加油站距離。對於 $r$ 的子樹 $(u, l)$ ，若

$l > d'$ 則明顯無解
$\mathsf{dfs}(u)+l>d'$ 則我們應設一個加油站在 $u$
最後，如果存在 $r$ 的兩個子樹 $(u, l_u)$ , $(v, l_v)$ 他們之間加油站的距離 $\mathsf{dfs}(u)+l_u+l_v+\mathsf{dfs}(v) > d'$ ，則我們應設一個加油站在 $r$ 。
該 $\mathsf{dfs}$ 可以在 $O(n)$ 的時間完成，二分搜尋法檢驗的範圍不大於 $\sum l$ ，因此整體時間複雜度為 $O(n\log \sum l)$ 。

说白了，只要每一颗子树都最小化加油站数量，然后我们再检测在最小化加油站数量前提下，是否违反了限制。

贪心的关键是，找到最优子结构。最优子结构是什么？就是在不在这贪取决于什么！

auto dfs=[&](auto && self,ll u,ll p) -> ll {
    ll dis=0;
    ll plus=0;
    for (auto [v,w]:g[u]) {
        if (v==p) continue;
        ll ldis=self(self,v,u);
        ldis+=w;
        // 如果说 ldis 本身就大于 d 这个门槛呢？那么给 v 节点加一个加油站
        if (ldis>d_threshold) {
            cnt_put++;
            ldis=w;
        }
        // 如果说，ldis 和 最远子节点距离 (mx)dis 之间大于了 d 呢？
        // 给 u 节点加一个加油站
        if (ldis+dis>d_threshold) {
            plus=1;
        }
        dis=max(dis,ldis);
    }
    cnt_put+=plus;
    if (plus) {
        return 0;
    }
    return dis;
};

AC代码

AC
https://codeforces.com/gym/106084/submission/361152548

源代码

/**
 * Problem: J. Gas Station
 * Contest: 2025 ICPC Asia Taiwan Online Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106084/problem/J
 * Created: 2026-02-02 18:55:51
 * 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 LD = long 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;

/*
 *
 */

void Solve() {
    ll N,K;
    cin >> N >> K;
    vector<vector<pair<ll,ll>>> g(N+2);
    ll sumw=0,mxw=0;
    for (int i=1;i<=N-1;++i) {
        ll u,v,w;
        cin>>u>>v>>w;
        sumw+=w;
        mxw=max(mxw,w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    ll l=mxw,r=sumw;
    ll cnt_put=0;
    ll d_threshold=0;
    auto dfs=[&](auto && self,ll u,ll p) -> ll {
        ll dis=0;
        ll plus=0;
        for (auto [v,w]:g[u]) {
            if (v==p) continue;
            ll ldis=self(self,v,u);
            ldis+=w;
            if (ldis>d_threshold) {
                cnt_put++;
                ldis=w;
            }
            if (ldis+dis>d_threshold) {
                plus=1;
            }
            dis=max(dis,ldis);
        }
        cnt_put+=plus;
        if (plus) {
            return 0;
        }
        return dis;
    };
    auto check=[&]() -> bool {
        cnt_put=0;
        dfs(dfs,1,-1);
        if (cnt_put > K) {
            return false;
        }
        return true;
    };
    while (l<r) {
        ll mid=l+r>>1;
        d_threshold=mid;
        if (check()) {
            r=mid;
        }else {
            l=mid+1;
        }
    }
    cout<<l<<"\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/106084/submission/361152548

*/

题目大意

思路讲解

AC代码

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

题目大意

思路讲解

AC代码

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

题目大意

思路讲解

1. 分子分析 (∬Df(t) dt\iint_D f(\mathbf{t}) \, d\mathbf{t}∬D​f(t)dt)

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

AC代码

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

题目大意

思路讲解

AC代码

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

核心思路：集合模拟（Set Simulation）

SPJ 的具体实现步骤

1. 基础校验 (Basic Validation)

2. 状态定义 (The Critical Point)

3. 状态转移 (Transition)

4. 碰撞检测 (Collision Check)

5. 终止条件 (Termination)

完整的 SPJ 代码结构 (基于 testlib.h)

总结

题目大意

思路讲解

Problem J - Gas Station

AC代码

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

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

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