Znzryb's Blog

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——G. Get Good

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

题目大意

题目总结：G. Get Good

基本参数

$n$ : 总天数。
$a$ : 处于“精力充沛”状态下每日获得的技能点。
$b$ : 处于“疲劳”状态下每日获得的技能点（ $a \ge b$ ）。
$x$ : 连续工作 $x$ 天后，状态从“精力充沛”转为“疲劳”。
$y$ : 连续休息 $y$ 天后，状态重置为“精力充沛”。

规则说明

初始状态：第 1 天开始时处于“精力充沛”状态。
工作机制：

前 $x$ 天工作，每天得 $a$ 分。
从第 $x+1$ 天起如果不休息继续工作，每天得 $b$ 分。

休息机制：随时可以开始连续休息 $y$ 天。休息期间得 0 分，休息结束后重新变为“精力充沛”状态（即又能享受 $x$ 天的高收益 $a$ ）。
目标：在 $n$ 天内通过合理安排工作与休息的时间，求最大化技能点总和。

样例解释

样例 2 ( $n=4, a=4, b=2, x=3, y=3$ )
- 方案 A：连续工作 4 天。前 3 天得 $3 \times 4 = 12$ ，第 4 天疲劳得 2，总分 $12+2=14$ 。
- 方案 B：工作 1 天后休息 3 天。总分 4。
- 最大值：14。
样例 3 ( $n=5, a=3, b=2, x=3, y=1$ )
- 方案 A：工作 5 天。前 3 天得 $3 \times 3 = 9$ ，后 2 天疲劳得 $2 \times 2 = 4$ ，总分 13。
- 方案 B：工作 3 天（得 9），休息 1 天，第 5 天重新精力充沛工作（得 3），总分 $9+0+3=12$ 。
- 最大值：13。
样例 4 ( $n=5, a=4, b=1, x=3, y=1$ )
- 由于疲劳收益 $b=1$ 太低，休息 1 天比疲劳工作更划算。
- 方案：工作 3 天（得 $3 \times 4 = 12$ ），休息 1 天（得 0），第 5 天重新开始工作（得 4），总分 $12+0+4=16$ 。
- 最大值：16。

思路讲解

ll N,a_fresh,b_tired,x_do,y_rest;
cin >> N>>a_fresh>>b_tired>>x_do>>y_rest;
// if (a_fresh==b_tired) {
//     cout<<N*a_fresh<<"\n";
//     return;
// }
ll l=N*b_tired,r=N*a_fresh;
ll ans=0;
do {
    ll num_a=min(x_do,N),num_b=N-num_a;
    ll lans=num_a*a_fresh+num_b*b_tired;
    ans=max(lans,ans);
}while (false);
do {
    ll num_a=N/(x_do+y_rest),rem=N-num_a*(x_do+y_rest);
    ll lans=num_a*x_do*a_fresh+min(rem,x_do)*a_fresh+
        (rem-min(rem,x_do))*b_tired;
    ans=max(lans,ans);
}while (false);
// 最后一段加上的原因见下：
do {
    ll num_a=N/(x_do+y_rest);
    ll rem=0;
    if (num_a>=1) {
        rem=N-num_a*(x_do+y_rest);
        rem+=y_rest;
    }else {
        rem=N-num_a*(x_do+y_rest);
    }
    ll lans=num_a*x_do*a_fresh+rem*b_tired;
    ans=max(lans,ans);
}while (false);
cout<<ans<<"\n";

b 和 a，x 的不同关系已经在前两种情况中包含了，但是 b 和 x+a+x 的关系还没有包含。

AC代码

源代码

/**
 * Problem: G. Get Good
 * Contest: 2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025)
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106157/problem/G
 * Created: 2026-02-06 12:20:41
 * 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,testcase;

/*
 *
 */

void Solve() {
    ll N,a_fresh,b_tired,x_do,y_rest;
    cin >> N>>a_fresh>>b_tired>>x_do>>y_rest;
    // if (a_fresh==b_tired) {
    //     cout<<N*a_fresh<<"\n";
    //     return;
    // }
    ll l=N*b_tired,r=N*a_fresh;
    ll ans=0;
    do {
        ll num_a=min(x_do,N),num_b=N-num_a;
        ll lans=num_a*a_fresh+num_b*b_tired;
        ans=max(lans,ans);
    }while (false);
    do {
        ll num_a=N/(x_do+y_rest),rem=N-num_a*(x_do+y_rest);
        ll lans=num_a*x_do*a_fresh+min(rem,x_do)*a_fresh+
            (rem-min(rem,x_do))*b_tired;
        ans=max(lans,ans);
    }while (false);
    do {
        ll num_a=N/(x_do+y_rest);
        ll rem=0;
        if (num_a>=1) {
            rem=N-num_a*(x_do+y_rest);
            rem+=y_rest;
        }else {
            rem=N-num_a*(x_do+y_rest);
        }
        ll lans=num_a*x_do*a_fresh+rem*b_tired;
        ans=max(lans,ans);
    }while (false);
    // if (a_fresh*x_do/(double)(x_do+y_rest)>b_tired/(double)(x_do+y_rest)) {
    //
    // }
    cout<<ans<<"\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://codeforces.com/gym/106157/submission/361663845
AC
https://qoj.ac/submission/2009999
1
4 4 2 3 3

1
2 2 2 2 2

*/

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

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——J. Joust Sort（拓扑排序解决依赖排序问题）

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

题目大意

题目总结：J. Joust排序 (Joust Sort)

题目核心：
给定一个由小写字母组成的字符串，以及若干条字母之间的“大小关系”约束。要求根据这些约束对字符串进行重新排列。

规则说明：

强约束： 若给定，则在最终字符串中，所有字母必须出现在所有字母之前。
无约束： 若字母和之间没有直接或间接的约束关系（既不是也不是），则它们在字符串中的位置可以任意交错。
合法性： 如果约束关系中存在冲突（如环状依赖且），则判定为无法排序。

输出要求：

输出满足所有约束的任意一种排列方案。
若不存在合法方案，输出 IMPOSSIBLE。

样例解释：

样例 1：
输入：m > i, n < i, i > o，字符串 minion。
推导：由且（即）可知，和都在之前。由（即）可知，在之前。
关系链：。
结果：noniim 符合。
样例 2：
输入：b < n，字符串 banana。
推导：仅要求所有的 b 在所有的 n 之前。对字母 a 没有约束。
结果：banana。此时所有的 b（位置0）确实在所有的 n（位置2, 4）之前，a 可以穿插其中。
样例 3：
输入：包含多条重复及推导关系，如且。
推导：关系链为。
结果：nnnbaaama。所有的 n 在 b 前，所有的 b 在 a 前。
样例 4：
输入：a < b, b < a。
推导：逻辑冲突，存在环。
结果：IMPOSSIBLE。

思路讲解

拓扑排序。

AC代码

AC
https://codeforces.com/gym/106157/submission/361649348

源代码

/**
 * Problem: J. Joust Sort
 * Contest: 2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025)
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106157/problem/J
 * Created: 2026-02-06 13:10:57
 * 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,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<vector<ll>> g(30);
    vector<ll> in_degree(30);
    for (int i=1;i<=N;++i) {
        char a,op,b;
        cin>>a>>op>>b;
        if (op=='<') {
            swap(a,b);
        }
        g[b-'a'].push_back(a-'a');
        in_degree[a-'a']++;
    }
    map<char,ll> ch_cnt;
    string s;
    cin>>s;
    for (auto &ch:s) {
        ch_cnt[ch]++;
    }
    vector<char> vis(30);
    string ans;
    auto topo_sort=[&](ll node) -> vector<ll> {
        queue<ll> q;
        vector<ll> res;
        vis[node]=true;
        q.push(node);
        res.push_back(node);
        while (!q.empty()) {
            ll u=q.front();
            q.pop();
            for (auto v:g[u]) {
                if (vis[v]) {
                    continue;
                }
                in_degree[v]--;
                if (in_degree[v]==0) {
                    vis[v]=true;
                    res.push_back(v);
                    q.push(v);
                }
            }
        }
        return res;
    };

    for (int i=0;i<26;++i) {
        if (vis[i]) {
            continue;
        }
        if (in_degree[i]==0) {
            vector<ll> res=topo_sort(i);
            for (auto id:res) {
                char a='a'+id;
                ans+=string(ch_cnt[a],a);
            }
        }
    }
    if (SZ(ans)!=SZ(s)) {
        cout<<"IMPOSSIBLE\n";
        return;
    }
    cout<<ans<<"\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://codeforces.com/gym/106157/submission/361649348

*/

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

小羊-2025-12-04-M. Ahmad's Dish（圆和正多边形的这个 minkowski 和）

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

题目大意

艾哈迈德对物理充满热情，最近他学到了一些新知识。

他知道，为了防止一个物体从桌子上掉下来，该物体的质心必须放在桌子上，即使该物体的其他部分在桌子外面。

艾哈迈德得知这个新概念后非常兴奋，于是他去找伊斯梅尔分享这个想法。

不幸的是，伊斯梅尔喜欢几何，而且学得很快，很快就理解了艾哈迈德的新想法，并给他出了一道好题。

这道题涉及一张半径为 $R$ 的圆桌和一个边长为 $N$ 、每边长为 $L$ 的正多边形盘子。

盘子的数量不受限制；盘子可以放在桌子上的任何地方，只要它们不从桌子上掉下来，并且至少有一边与 x 轴平行。

我们的任务是找出这些盘子所能覆盖的最大面积。

在上例 $R = 4, N = 4, L = 2$ 中。紫色的形状就是盘子所能覆盖的最大面积。

作为阿默德的好朋友，你想帮助他解决这个问题。

思路讲解

把正方形在圆上移动，看成圆在正方形上移动，因为

正多边形面积公式， $n$ 是这个边数， $l$ 是边长。

A = \frac{n \cdot l^2}{4 \cdot \tan(\frac{\pi}{n})}

void Solve() {
    ll R,N,L;
    cin >> R >> N >> L;
    // 加上平移的得到的长方形
    DB ans=N*R*L;
    //  加上一个圆
    ans+=pi*R*R;
    ans+=N*L*L/(4*tan(pi/N));
    cout<<fsp(10)<<ans<<"\n";
}

AC代码

AC
https://codeforces.com/gym/104493/submission/361481631

源代码

/**
 * Problem: M. Ahmad's Dish
 * Contest: 2023 ICPC HIAST Collegiate Programming Contest
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/104493/problem/M
 * Created: 2026-02-05 10:18: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,testcase;

/*
 *
 */

void Solve() {
    ll R,N,L;
    cin >> R >> N >> L;
    DB ans=N*R*L;
    ans+=pi*R*R;
    ans+=N*L*L/(4*tan(pi/N));
    cout<<fsp(10)<<ans<<"\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://codeforces.com/gym/104493/submission/361481631


*/

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

给定一个含有 $n$ 个顶点和 $m$ 条边的森林。假设该森林有 $k$ 个连通块，其大小分别为 $s_1, s_2, \dots, s_k$ 。已知将该森林添加 $k-1$ 条边使其成为一棵树的方案总数为：

如果还有二分图，则可以进一步变为这个 $|dis_u-dis_v|= 1$ ，原因如下

二分图的作用就在这里：二分图等价于“所有环长度为偶数”，也等价于“从固定根出发的最短路距离奇偶性给出一个合法二分划分”。因此对任意边 $(u,v)$ ，必有 $dis_u$ 与 $dis_v$ 奇偶性相反，也就是 $dis_u\ne dis_v$ 。

/*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;
    size_t n = poly.size();
    for (int i = 0; i < n; ++i) {
        res += cross(poly[i], poly[(i + 1) % n]);
    }
    res = abs(res) / 2.0;
    return res;
}

DB polygon_perimeter(const vector<Point> &poly) {
    DB res = 0;
    size_t n = poly.size();
    for (int i = 0; i < n; ++i) {
        res += (poly[i] - poly[(i + 1) % n]).abs();
    }
    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;
}

vector<Point> make_convex_hull(vector<Point> A) {
    size_t n = A.size();
    if (n <= 2) {
        // 特判
        return A;
    }
    vector<Point> ans(n * 2);
    // Andrew 算法的核心：先按 X 坐标排序，X 相同按 Y 坐标排序
    // 这样我们就可以保证处理点的顺序是从左到右
    sort(A.begin(), A.end());
    int now = -1;
    for (int i = 0; i < n; i++) {
        // 维护下凸包
        // 这个是严格的，不保存共线点的实现
        // 只有严格大于 0 的时候才是这个 CCW 的
        while (now > 0 && cross(ans[now] - A[i], ans[now - 1] - A[i]) <= 0) {
            now--; // 弹出栈顶，因为它会导致凹陷或共线
        }
        ans[++now] = A[i];
    }
    int pre = now;
    // 从右向左扫描所有点（注意是从 n-2 开始，因为 n-1 已经在栈顶了）
    for (int i = n - 2; i >= 0; i--) {
        // 维护上凸包
        while (now > pre && cross(ans[now] - A[i], ans[now - 1] - A[i]) <= 0) {
            now--;
        }
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}

The 2025 ICPC Asia East Continent Online Contest (II) ICPC网络赛第二场——A. Angry Birds

Posted on 2026-02-04 Edited on 2026-03-03

题目大意

题目总结

基本设定

空间：三维欧几里得空间，建立 $O-xyz$ 坐标系。
对象：小鸟是一个半径为 $R_3$ 的球体。
运动平面：小鸟球心的运动轨迹始终位于 $z=0$ 的水平面上。

轨迹定义

闭合折线：小鸟球心的轨迹是由 $n$ 个点按顺序连接而成的闭合折线（第 $n$ 点连回第 $1$ 点）。
传感器误差（关键条件）：
- 给定了 $n$ 个基准坐标 $(x_i, y_i, 0)$ 。
- 实际的第 $i$ 个折线端点 $(x'_i, y'_i, 0)$ 并不固定，它可以位于以 $(x_i, y_i, 0)$ 为圆心、半径为 $R_2$ 的圆盘（ $z=0$ 面内）中的任意位置。

目标问题

定义集合 $S$ 为小鸟在所有可能的轨迹情况（即考虑端点在 $R_2$ 误差圆内任意变动）下，球体可能经过的所有空间点的集合。
求集合 $S$ 的凸包体积。

输入输出

输入： $T$ 组数据。每组包含 $n$ （点数）， $R_2$ （误差半径）， $R_3$ （小鸟半径），以及 $n$ 个基准点的二维坐标。
输出：凸包的体积（浮点数）。

样例解释

以样例为例：

输入： $n=5$ 个点，误差半径 $R_2=1$ ，小鸟半径 $R_3=1$ 。
基准点： $(0,0), (3,1), (2,3), (2,2), (-1,3)$ 。
几何理解：你需要想象这 5 个点，每个点都代表一个半径为 1 的“误差圆”。实际轨迹的折点可以在这些圆内任意取。小鸟本身又是半径为 1 的球。
求解目标：计算包含所有这些可能性的最小凸多面体的体积。最终输出约为 77.622211120429589。

思路讲解

Video

void Solve() {
    ll N,R_deviate,R_bird;
    cin >> N >> R_deviate >> R_bird;

    vector<Point> poly(N);
    for (int i=0;i<N;++i) {
        cin>>poly[i];
    }
    // 先找到一个二维凸包
    poly=make_convex_hull(poly);
    // 凸包面积
    DB ans=polygon_area(poly);
    // 凸包和圆 deviate 的 minkowski 和
    auto perimeter=polygon_perimeter(poly);
    ans+=perimeter*R_deviate+pi*R_deviate*R_deviate;
    // ans+=perimeter*R_deviate+pi*(R_deviate+R_bird)*(R_deviate+R_bird);

    // minkowski 和 的体积（底乘高）
    ans*=2*R_bird;
    // 球体体积
    ans+=4/3.0*pi*R_bird*R_bird*R_bird;
    // 为什么这个高亮部分需要加上去？这个是这道题目的难点。
    ans+=(pi*R_bird*R_bird*(perimeter+pi*R_deviate*2))/2.0;
    cout<<fsp(12)<<ans<<"\n";
}

为什么这个高亮部分（piR_deviate2）需要加上去？这个是这道题目的难点。**

其实是对的，因为圆其实是一个边缘面积

Video

AC代码

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

源代码

/**
 * Problem: A. Angry Birds
 * Contest: The 2025 ICPC Asia EC Regionals Online Contest (II)
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106072/problem/A
 * Created: 2026-02-04 19:57:44
 * 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 = 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;

/*
 *
 */
/*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 polygon_area(const vector<Point> &poly) {
    DB res = 0;
    size_t n = poly.size();
    for (int i = 0; i < n; ++i) {
        res += cross(poly[i], poly[(i + 1) % n]);
    }
    res = abs(res) / 2.0;
    return res;
}

DB polygon_perimeter(const vector<Point> &poly) {
    DB res = 0;
    size_t n = poly.size();
    for (int i = 0; i < n; ++i) {
        res += (poly[i] - poly[(i + 1) % n]).abs();
    }
    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;
}

vector<Point> make_convex_hull(vector<Point> A) {
    size_t n = A.size();
    if (n <= 2) {
        // 特判
        return A;
    }
    vector<Point> ans(n * 2);
    // Andrew 算法的核心：先按 X 坐标排序，X 相同按 Y 坐标排序
    // 这样我们就可以保证处理点的顺序是从左到右
    sort(A.begin(), A.end());
    int now = -1;
    for (int i = 0; i < n; i++) {
        // 维护下凸包
        // 这个是严格的，不保存共线点的实现
        // 只有严格大于 0 的时候才是这个 CCW 的
        while (now > 0 && cross(ans[now] - A[i], ans[now - 1] - A[i]) <= 0) {
            now--; // 弹出栈顶，因为它会导致凹陷或共线
        }
        ans[++now] = A[i];
    }
    int pre = now;
    // 从右向左扫描所有点（注意是从 n-2 开始，因为 n-1 已经在栈顶了）
    for (int i = n - 2; i >= 0; i--) {
        // 维护上凸包
        while (now > pre && cross(ans[now] - A[i], ans[now - 1] - A[i]) <= 0) {
            now--;
        }
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}

void Solve() {
    ll N,R_deviate,R_bird;
    cin >> N >> R_deviate >> R_bird;

    vector<Point> poly(N);
    for (int i=0;i<N;++i) {
        cin>>poly[i];
    }
    // 先找到一个二维凸包
    poly=make_convex_hull(poly);
    // 凸包面积
    DB ans=polygon_area(poly);
    // 凸包和圆 deviate 的 minkowski 和
    auto perimeter=polygon_perimeter(poly);
    ans+=perimeter*R_deviate+pi*R_deviate*R_deviate;
    // ans+=perimeter*R_deviate+pi*(R_deviate+R_bird)*(R_deviate+R_bird);

    // minkowski 和 的体积（底乘高）
    ans*=2*R_bird;
    ans+=4/3.0*pi*R_bird*R_bird*R_bird;
    ans+=(pi*R_bird*R_bird*(perimeter+pi*R_deviate*2))/2.0;
    cout<<fsp(12)<<ans<<"\n";
}

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

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

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

*/

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

82. 二维凸包（Andrew 安德鲁单调链算法）

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

题目大意

思路讲解

vector<Point> make_convex_hull(vector<Point> A) {
    size_t n = A.size();
    if (n <= 2) {
        // 特判
        return A;
    }
    vector<Point> ans(n * 2);
    // Andrew 算法的核心：先按 X 坐标排序，X 相同按 Y 坐标排序
    // 这样我们就可以保证处理点的顺序是从左到右
    sort(A.begin(), A.end());
    int now = -1;
    for (int i = 0; i < n; i++) {
        // 维护下凸包
        // 这个是严格的，不保存共线点的实现
        // 只有严格大于 0 的时候才是这个 CCW 的
        while (now > 0 && cross(ans[now] - A[i], ans[now - 1] - A[i]) <= 0) {
            now--; // 弹出栈顶，因为它会导致凹陷或共线
        }
        ans[++now] = A[i];
    }
    int pre = now;
    // 从右向左扫描所有点（注意是从 n-2 开始，因为 n-1 已经在栈顶了）
    for (int i = n - 2; i >= 0; i--) {
        // 维护上凸包
        while (now > pre && cross(ans[now] - A[i], ans[now - 1] - A[i]) <= 0) {
            now--;
        }
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}

AC代码

源代码

/**
 * Problem: 二维凸包
 * Contest: QOJ
 * Judge: Virtual Judge
 * URL: https://vjudge.net/problem/QOJ-218
 * Created: 2026-02-04 20:10:41
 * 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;
    size_t n = poly.size();
    for (int i = 0; i < n; ++i) {
        res += cross(poly[i], poly[(i + 1) % n]);
    }
    res = abs(res) / 2.0;
    return res;
}

DB polygon_perimeter(const vector<Point> &poly) {
    DB res = 0;
    size_t n = poly.size();
    for (int i = 0; i < n; ++i) {
        res += (poly[i] - poly[(i + 1) % n]).abs();
    }
    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;
}

vector<Point> make_convex_hull(vector<Point> A) {
    size_t n = A.size();
    if (n <= 2) {
        // 特判
        return A;
    }
    vector<Point> ans(n * 2);
    // Andrew 算法的核心：先按 X 坐标排序，X 相同按 Y 坐标排序
    // 这样我们就可以保证处理点的顺序是从左到右
    sort(A.begin(), A.end());
    int now = -1;
    for (int i = 0; i < n; i++) {
        // 维护下凸包
        // 这个是严格的，不保存共线点的实现
        // 只有严格大于 0 的时候才是这个 CCW 的
        while (now > 0 && cross(ans[now] - A[i], ans[now - 1] - A[i]) <= 0) {
            now--; // 弹出栈顶，因为它会导致凹陷或共线
        }
        ans[++now] = A[i];
    }
    int pre = now;
    // 从右向左扫描所有点（注意是从 n-2 开始，因为 n-1 已经在栈顶了）
    for (int i = n - 2; i >= 0; i--) {
        // 维护上凸包
        while (now > pre && cross(ans[now] - A[i], ans[now - 1] - A[i]) <= 0) {
            now--;
        }
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}

void Solve() {
    ll N;
    cin >> N;
    vector<Point> poly(N);
    for (int i = 0; i < N; ++i) {
        cin >> poly[i];
    }
    auto res_poly = make_convex_hull(poly);
    cout << fsp(16) << polygon_perimeter(res_poly) << "\n";
}

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

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

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

0094551429903350
*/