洛谷P2742 【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows
题目大意
给定平面上 n 个点，求能围住所有点的最小凸多边形周长。
数据范围：1 ≤ n ≤ 10^5，坐标 |xi|, |yi| ≤ 10^6，小数点后最多两位。
分析
问题等价于求这些点的凸包周长。
n 较大，需要 O(n log n) 的凸包算法。
Andrew 算法是一种经典解法，通过排序和两次扫描得到凸包顶点，时间复杂度 O(n log n)。
Andrew 算法描述
- 排序：将所有点按 x 坐标为第一关键字、y 坐标为第二关键字升序排序。排序后的第一个点和最后一个点一定在凸包上。
- 构造下凸包：从最左到最右顺序扫描每个点，用栈维护当前凸包上的点。对于新点，不断检查栈顶两点与新点构成的向量的叉积，如果叉积 ≤ 0（表示新点在栈顶两点连线的右侧或共线），则弹出栈顶，直到满足左转关系，然后将新点入栈。
- 构造上凸包：从最右到最左逆序扫描每个点（排除已经用过的首尾点），同样用栈维护，但需保证栈大小不小于下凸包的点数，避免重复。扫描结束后，栈中存储了凸包的所有顶点（首尾重复一次）。
最后，计算相邻顶点间的距离之和即得凸包周长。
代码解释（对应已给出的 AC 代码）
结构体 Point：存储点的 x, y 坐标。
叉积函数 cross(a, b, c)：计算向量 ab 与 ac 的叉积，用于判断转向。若返回值 ≤ 0 表示在右侧或共线。
距离函数 dis(a, b)：计算两点欧氏距离。
排序比较函数 comp：按 x 升序，x 相同则按 y 升序。
Andrew 函数：
传入点的数量 n 和栈顶指针初始值 0。
首先对所有点排序（下标从 1 开始）。
下凸包：遍历 i = 1 到 n，在栈中维护下凸包。当栈顶至少有两个点且新点与栈顶两点叉积 ≤ 0 时，弹出栈顶，然后将当前点入栈。
记录此时栈大小 t，表示下凸包的点数。
上凸包：从 i = n-1 到 1 逆序遍历，同样用栈维护，但需保证栈大小始终大于 t，以免破坏下凸包。条件仍然是叉积 ≤ 0 时弹出。
扫描结束后，栈中从 1 到 top-1 存储了凸包的所有顶点（首尾重复一次，即起点在栈中出现了两次）。
最后计算周长：遍历 i = 1 到 top-1，累加 ss[i] 到 ss[i+1] 的距离。
主函数 solve：
读入 n 和所有点坐标。
调用 Andrew 得到周长，保留两位小数输出。
时间复杂度
排序：O(n log n)
凸包扫描：每个点最多入栈两次、出栈两次，总操作 O(n)
总复杂度 O(n log n)，在 n = 10^5 时完全可行。
总结
本题是凸包模板题，Andrew 算法实现简洁，利用叉积判断转向，通过两次扫描得到凸包顶点。注意处理共线情况时，题目通常要求凸包顶点不包含边上的中间点，因此弹出条件为 ≤ 0 而非 < 0。最终周长计算注意浮点数精度，保留两位小数输出
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0)
#define pll pair<ll,ll>
const ll N = 1e5 + 5;struct Point{double x,y;
}pp[N],ss[N];double cross(Point a, Point b, Point c){//叉乘return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
double dis(Point a, Point b){//距离return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}bool comp(Point a, Point b){//比较return a.x != b.x ? a.x < b.x : a.y < b.y;
}double Andrew(ll n, ll top){sort(pp + 1, pp + n + 1, comp);for(ll i = 1; i <= n; i++){//下凸包while(top > 1 && cross(ss[top - 1],ss[top],pp[i]) <= 0) top--;ss[++top] = pp[i];}ll t = top;for(ll i = n - 1; i >= 1; i--){//上凸包while(top > t && cross(ss[top - 1],ss[top],pp[i]) <= 0) top--;ss[++top] = pp[i];}double res = 0;for(ll i = 1; i < top; i++){res += dis(ss[i],ss[i + 1]);}return res;
}void solve(){ll n,top = 0;cin >> n;for(ll i = 1; i <= n; i++){cin >> pp[i].x >> pp[i].y;}double ans = Andrew(n,top);cout<<fixed<<setprecision(2)<<ans<<endl;return;
}int main(){fast;ll t = 1; //cin >> t;while(t--){solve();}return 0;
}