POJ 1113 凸包

题意

传送门 POJ 1113

题解

求城堡的凸包，再加上半径为最小距离的圆的周长（保证顶点与围栏的最小距离）即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define min(a,b)    (((a) < (b)) ? (a) : (b))
#define max(a,b)    (((a) > (b)) ? (a) : (b))
#define abs(x)    ((x) < 0 ? -(x) : (x))
#define INF 0x3f3f3f3f
#define delta 0.85
#define eps 1e-8
#define PI 3.14159265358979323846
using namespace std;

double EPS = 1e-10;

// 考虑误差的加法运算
double add(double a, double b){
	if(abs(a + b) < EPS * (abs(a) + abs(b))) return 0;
	return a + b;
}

// 二维向量结构体
struct P{
	double x, y;
	P(){}
	P(double x, double y) : x(x), y(y) {}
	P operator + (P p){
		return P(add(x, p.x), add(y, p.y));
	}
	P operator - (P p){
		return P(add(x, -p.x), add(y, -p.y));
	}
	P operator * (double d){
		return P(x * d, y * d);
	}
	double dot(P p){	// 内积
		return add(x * p.x, y * p.y);
	}
	double det(P p){	// 外积
		return add(x * p.y, -y * p.x);
	}
};

// 字典序比较
bool cmp_x(const P& p, const P& q){
	if(p.x != q.x) return p.x < q.x;
	return p.y < q.y;
}

// 求凸包
vector<P> convex_hull(P* ps, int n){
	sort(ps, ps + n, cmp_x);
	int k = 0;				// 凸包的顶点数
	vector<P> qs(n * 2);	// 构造中的凸包
	// 构造凸包的下侧
	for(int i = 0; i < n; i++){
		while(k > 1 && (qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1]) <= 0) k--;
		qs[k++] = ps[i];
	}
	// 构造凸包的上侧
	for(int i = n - 2, t = k; i >= 0; i--){
		while(k > t && (qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1]) <= 0) k--;
		qs[k++] = ps[i];
	}
	//qs.reszie(k - 1);
	qs.resize(k);	// 第一个点重复加入凸包
	return qs;
}

// 距离
double dist(P p, P q){
	return sqrt((p - q).dot(p - q));
}

#define MAX_N 1000
int N, L;
P ps[MAX_N];

void solve(){
	vector<P> qs = convex_hull(ps, N);
	double res = 2 * PI * L;
	for(int i = 1; i < qs.size(); i++) res += dist(qs[i], qs[i - 1]);
	printf("%.0f\n", res);
}

int main(){
	int t = 0;
	while(~scanf("%d%d", &N, &L)){
		for(int i = 0; i < N; i++) scanf("%lf%lf", &ps[i].x, &ps[i].y);
		solve();
	}
	return 0;
}