Andrew ConvexHull

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include<bits/stdc++.h> 

using namespace std;

const int M = 105;

struct Point {
    double x{}, y{};
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    //	{this->x=x, this->y=y;}
    Point operator+(Point t) const { return {x + t.x, y + t.y}; }
    Point operator-(Point t) const { return {x - t.x, y - t.y}; }
    bool operator==(Point t) const { return x == t.x && y == t.y; }
    bool operator<(const Point &t) const {
        if (x != t.x) return x < t.x;
        return y < t.y;
    }
};

Point a[M], b[M];//a存放所有的点，b存放凸包上的点

//a和b都是向量
double cross(Point a, Point b) {
    /*
        若a * b >0，则a在b的右边；
        若a * b <0,  则a在b的左边；
        若a * b = 0, 则a和b共线(有可能同向，有可能反向)；
    */
    return a.x * b.y - a.y * b.x;
}

double distance(Point a, Point b) {
    return hypot(a.x - b.x, a.y - b.y);
}

int solve(int n) {
    sort(a, a + n);
    n = unique(a, a + n) - a;

    //求下凸包
    int v = 0;
    for (int i = 0; i < n; i++) {
        while (v > 1 && cross(b[v - 1] - b[v - 2], a[i] - b[v - 2]) <= 0.0) v--;
        b[v++] = a[i];
    }

    //求上凸包
    int j = v;
    for (int i = n - 2; i >= 0; i--) {
        while (v > j && cross(b[v - 1] - b[v - 2], a[i] - b[v - 2]) <= 0.0) v--;
        b[v++] = a[i];
    }

    return n > 1 ? v - 1 : v;//v是b里面的顶点数
}

int main() {
    int n;
    while (cin >> n && n) {
        for (int i = 0; i < n; i++)
            cin >> a[i].x >> a[i].y;

        int k = solve(n);
        double ans = 0.0;

        if (k == 1) ans = 0.0;
        else if (k == 2) ans = distance(a[0], a[1]);
        else
            for (int i = 0; i < k; i++)
                ans += distance(b[i], b[(i + 1) % k]);
        // cout<<k<<endl;
        printf("%.2lf\n", ans);
    }

    return 0;
}