题意：给一堆二维的点，问你最少用多少距离能把这些点都围起来
思路：
凸包：
我们先找到所有点中最左下角的点p1，这个点绝对在凸包上。接下来对剩余点按照相对p1的角度升序排序，角度一样按距离升序排序。因为凸包有一个特点，从最左下逆时针走，所有线都在当前这条向量的左边，根据这个特点我们进行判断。我们从栈顶拿出两个点s[top-1]，s[top]，所以如果s[top-1] -> p[i] 在 s[top-1] -> s[top] 右边，那么s[top]就不是凸包上一点，就这样一直判断下去。判断左右可以用叉乘。
参考：数学：凸包算法详解
模板（考虑n <= 2）：
struct node{
double x, y;
}p[maxn], s[maxn];
int n, top;
double dis(node a, node b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool cmp(node a, node b){
double A = atan2((a.y - p[].y), (a.x - p[].x));
double B = atan2((b.y - p[].y), (b.x - p[].x));
if(A != B) return A < B;
else{
return dis(a, p[]) < dis(b, p[]);
}
}
double cross(node a, node b, node c){ //(a->b)X(a->c)
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
void solve(){
int pos = ;
for(int i = ; i <= n; i++){
if(p[i].y < p[pos].y || (p[i].y == p[pos].y && p[i].x < p[pos].x)){
pos = i;
}
}
swap(p[], p[pos]);
sort(p + , p + n + , cmp);
s[] = p[], s[] = p[];
top = ;
for(int i = ; i <= n; i++){
while(top >= && cross(s[top - ], p[i], s[top]) >= ){ //向右转出栈
top--;
}
s[++top] = p[i];
}
}
代码：
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = + ;
const int MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
struct node{
double x, y;
}p[maxn], s[maxn];
int n, top;
double dis(node a, node b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool cmp(node a, node b){
double A = atan2((a.y - p[].y), (a.x - p[].x));
double B = atan2((b.y - p[].y), (b.x - p[].x));
if(A != B) return A < B;
else{
return dis(a, p[]) < dis(b, p[]);
}
}
double cross(node a, node b, node c){ //(a->b)X(a->c)
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
void solve(){
int pos = ;
for(int i = ; i <= n; i++){
if(p[i].y < p[pos].y || (p[i].y == p[pos].y && p[i].x < p[pos].x)){
pos = i;
}
}
swap(p[], p[pos]);
sort(p + , p + n + , cmp);
s[] = p[], s[] = p[];
top = ;
for(int i = ; i <= n; i++){
while(top >= && cross(s[top - ], p[i], s[top]) >= ){ //向左转出栈
top--;
}
s[++top] = p[i];
}
}
int main(){
while(~scanf("%d", &n) && n){
for(int i = ; i <= n; i++){
scanf("%lf%lf", &p[i].x, &p[i].y);
}
if(n == ){
printf("0.00\n");
continue;
}
if(n == ){
printf("%.2lf\n", dis(p[], p[]));
continue;
}
solve();
double ans = ;
for(int i = ; i < top; i++){
ans += dis(s[i], s[i + ]);
}
ans += dis(s[top], s[]);
printf("%.2lf\n", ans);
}
return ;
}