POJ 1113 Wall(凸包)

题意：求城堡外面距离为L的城墙的周长，思路就是这个距离为L的城墙就是这个城堡的凸包的长度加上以L为半径的一个圆（扫了一周）。

 

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#define N 1001
const double PI = 3.141592654;
using namespace std;
struct node{
	double x, y;
	bool friend operator < (const node &a, const node &b){
		if(a.y == b.y)
			return a.x < b.x;
		return a.y < b.y;
	}
}point[N];

double calcurateDis(node a, node b){
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

bool judge(node a, node b, node c){
	return (a.x - c.x)*(b.y - c.y) >= (b.x - c.x)*(a.y - c.y);
}

double solve(int n){
	vector<node> tempPoint(n*2);
	sort(point, point + n);
	if(n == 0) return 0;
	if(n == 1){
		return 0;
	}
	if(n == 2){
		return calcurateDis(point[0], point[1]);
	}
	tempPoint[0] = point[0];
	tempPoint[1] = point[1];
	tempPoint[2] = point[2];
	int top = 1;
	for(int i = 2; i < n; i++){
		while(top != 0 && judge(point[i], tempPoint[top], tempPoint[top - 1]))	top--;
		tempPoint[++top] = point[i];
	}
	int len = top;
	tempPoint[++top] = point[n - 2];
	for(int i = n - 3; i >= 0; i--){
		while(top != len && judge(point[i], tempPoint[top], tempPoint[top - 1]))	top--;
		tempPoint[++top] = point[i];
	}
	double result = 0.0;
	for(int i = 1; i <= top; i++){
		result += calcurateDis(tempPoint[i], tempPoint[(i + 1) > top ? 1 : (i + 1)]);
	}
	return result;
}

int main(){
	int n, L;
	scanf("%d%d", &n, &L);
	for(int i = 0; i < n; i++)
		scanf("%lf%lf", &point[i].x, &point[i].y);
	printf("%.0f\n", solve(n) + 2 * PI * L);
	return 0;
}