82. 二维凸包（Andrew 安德鲁单调链算法） · znzryb
## 题目大意
## 思路讲解
```cpp
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代码
::: 源代码
```cpp
/**
* 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
*/
```
:::
## 心路历程（WA，TLE，MLE……）