POJ 1113

1113.cpp

#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;

#define PI 3.1415926535
typedef pair<int, int> Pair;

int n;
int l;
int k;
int _k;
double ans;
Pair ps[1000];
Pair hull[2000];

inline Pair sub(Pair p1, Pair p2) {
    return Pair(p1.first-p2.first, p1.second-p2.second);
}

inline int det(Pair p1, Pair p2) {
    return p1.first * p2.second - p2.first * p1.second;
}

inline double dist(Pair p1, Pair p2) {
    int x = p1.first - p2.first;
    int y = p1.second - p2.second;

    return sqrt(x*x + y*y);
}

int main() {
    scanf("%d%d", &n, &l);
    for (int i=0; i<n; i++) {
        int x, y;

        scanf("%d %d", &x, &y);
        ps[i] = Pair(x, y);
    }

    sort(ps, ps+n);
    k = 0;
    for (int i=0; i<n; i++) {
        while (k > 1 && 
            det(sub(ps[i], hull[k-1]), sub(hull[k-2], hull[k-1])) <= 0) k--;
        hull[k++] = ps[i];
    }

    _k = k;
    for (int i=n-2; i>=0; i--) {
        while (k > _k && 
            det(sub(ps[i], hull[k-1]), sub(hull[k-2], hull[k-1])) <= 0) k--;
        hull[k++] = ps[i];
    }
    k--;

    ans = 2 * PI * l;
    for (int i=0; i<k; i++) {
        ans += dist(hull[(k+i-1)%k], hull[i]);
    }

    printf("%d\n", (int)(ans+0.5));
}