POJ 1113 Wall 题解 《挑战程序设计竞赛》

POJ 1113 Wall

墙：有个愚蠢的皇帝要你造墙将城堡围起来，城堡的顶点有N个，墙必须离城堡的边至少L单位远，并且墙的总长度尽量小。求此长度？

3.6与平面和空间打交道的计算几何 

凸包 

因为墙的长度要尽量短，所以墙不能凹进去。如图，最终的墙类似虚线部分，由凸包的周长和一个半径L的圆构成，于是求出凸包就搞定了。另外，题目阉割了英寸转换，用中文注明了“结果四舍五入就可以了”，估计要坑死一堆歪果仁。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

#define MAX_N 1000 + 16
#define M_PI 3.14159265358979323846

typedef int type_xy;
struct P
{
	type_xy x, y;
	P() {}
	P(type_xy x, type_xy y) : x(x), y(y) {}
	P operator + (P p){ return P(x + p.x, y + p.y); }
	P operator - (P p){ return P(x - p.x, y - p.y); }
	P operator * (type_xy d){ return P(x*d, y*d); }
	bool operator < (const P& a) const
	{
		if (x != a.x) return x < a.x;
		else return y < a.y;
	}
	type_xy dot(P p) { return x*p.x + y*p.y; }
	type_xy det(P p) { return x*p.y - y*p.x; }
};

// 字典序比较
bool cmp_x(P a, P b)
{
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.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.resize(k - 1);
	return qs;
}

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

// 求解凸包对踵点最大距离
double max_distance(P *ps, int N)
{
	vector<P> qs = convex_hull(ps, N);
	int n = qs.size();
	if (n == 2)
	{
		return dist(qs[0], qs[1]);	// 特别处理凸包退化的情况
	}
	int i = 0, j = 0;	// 某个方向上的对踵点对
	// 求出x轴方向上的对踵点对
	for (int k = 0; k < n; k++)
	{
		if (!cmp_x(qs[i], qs[k])) i = k;
		if (cmp_x(qs[j], qs[k])) j = k;
	}
	double res = 0;
	int si = i, sj = j;
	while (i != sj || j != si)	// 将方向逐步旋转180度
	{
		res = max(res, dist(qs[i], qs[j]));
		// 判断先转到边i-(i+1)的法线方向还是边j-(j+1)的法线方向
		if ((qs[(i + 1) % n] - qs[i]).det(qs[(j + 1) % n] - qs[j]) < 0)
		{
			i = (i + 1) % n;	//  先转到边i-(i+1)的法线方向
		}
		else
		{
			j = (j + 1) % n;	// 先转到边j-(j+1)的法线方向
		}
	}
	return res;
}

// 求解凸包周长
double total_distance(P *ps, int N)
{
	vector<P> qs = convex_hull(ps, N);
	int n = qs.size();
	double res = 0;
	for (int i = 0; i < n; ++i)
	{
		res += dist(qs[i], qs[(i + 1) % n]);
	}

	return res;
}

P ps[MAX_N];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N, L;
	while (~scanf("%d%d", &N, &L))
	{
		for (int i = 0; i < N; ++i)
		{
			scanf("%d%d", &ps[i].x, &ps[i].y);
		}
		double ans = (2 * M_PI * L + total_distance(ps, N));
		printf("%.0lf\n", ans);
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 1113 Wall 题解 《挑战程序设计竞赛》