HDU 1392 Surround the Trees（凸包）题解

题意：给一堆二维的点，问你最少用多少距离能把这些点都围起来

思路：

凸包：

我们先找到所有点中最左下角的点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[1].y), (a.x - p[1].x));
    double B = atan2((b.y - p[1].y), (b.x - p[1].x));
    if(A != B) return A < B;
    else{
        return dis(a, p[1]) < dis(b, p[1]);
    }
}
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 = 1;
    for(int i = 2; 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[1], p[pos]);
    sort(p + 2, p + n + 1, cmp);
    s[0] = p[1], s[1] = p[2];
    top = 1;
    for(int i = 3; i <= n; i++){
        while(top >= 1 && cross(s[top - 1], p[i], s[top]) >= 0){ //向右转出栈
            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 = 150 + 10;
const int MOD = 1e9 + 7;
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[1].y), (a.x - p[1].x));
    double B = atan2((b.y - p[1].y), (b.x - p[1].x));
    if(A != B) return A < B;
    else{
        return dis(a, p[1]) < dis(b, p[1]);
    }
}
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 = 1;
    for(int i = 2; 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[1], p[pos]);
    sort(p + 2, p + n + 1, cmp);
    s[0] = p[1], s[1] = p[2];
    top = 1;
    for(int i = 3; i <= n; i++){
        while(top >= 1 && cross(s[top - 1], p[i], s[top]) >= 0){ //向左转出栈
            top--;
        }
        s[++top] = p[i];
    }
}
int main(){
    while(~scanf("%d", &n) && n){
        for(int i = 1; i <= n; i++){
            scanf("%lf%lf", &p[i].x, &p[i].y);
        }
        if(n == 1){
            printf("0.00
");
            continue;
        }
        if(n == 2){
            printf("%.2lf
", dis(p[1], p[2]));
            continue;
        }
        solve();
        double ans = 0;
        for(int i = 0; i < top; i++){
            ans += dis(s[i], s[i + 1]);
        }
        ans += dis(s[top], s[0]);
        printf("%.2lf
", ans);
    }
    return 0;
}