Graham扫描法 凸包

一，思想：

             首先选取所有点中y坐标最小（y坐标相同的话选x最小的）的一个点，以这一个点为基点，计算其它点与这点的连线与x轴夹角的大小，按从小到大排序，排序后之后最小的一个点肯定在凸包上，最后依次对每一个点进行判断，具体看代码，

以http://acm.hdu.edu.cn/showproblem.php?pid=1348这个问题为例：

#include<bits/stdc++.h>
using namespace std;

#define MAXN 1000+10
#define pi acos(-1.0)
int N, r;
struct point { int x, y; }p[MAXN],po[MAXN];

double X(point A, point B, point C) { return (C.x - A.x)*(B.y - A.y) - (B.x - A.x)*(C.y - A.y); }//两向量的X乘

double get_dis(point A, point B) { return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y)); }//两点间的距离

bool cmp(point A,point B) {				//排序的规则
	double res = X(p[0], A, B);
	if (res > 0)return true;
	if (res < 0)return false;
	return get_dis(p[0], A) < get_dis(p[0], B);  //如果这两点与p[0]共线，距离小的放在前面
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int t; cin >> t;
	for (int cas = 1; cas <= t;cas++) {
		if (cas != 1)cout << endl;
		cin >> N>>r;
		
		for (int i = 0; i < N; i++) {
			cin >> p[i].x >> p[i].y;
		}

		double ans = 2 * pi*r;

		if (N == 1) {
			cout << int(ans + 0.5) << endl;
		}
		else if (N == 2) {
			cout << int(ans + get_dis(p[0], p[1]) + 0.5) << endl;
		}
		else {
			for (int i = 1; i < N; i++) {			//选取基点
				if (p[i].y < p[0].y)swap(p[i],p[0]);
				else if (p[i].y == p[0].y) {
					if (p[i].x < p[0].x)swap(p[i],p[0]);
				}
			}

			sort(p + 1, p + N,cmp);
			po[0] = p[0];				//排序好之后p[0]和p[1]肯定在凸包上
			po[1] = p[1];
			int tot = 1;
			for (int i = 2; i < N; i++) {
				while (tot > 0 && X(po[tot - 1], po[tot], p[i]) < 0)tot--; //如果p[i]在p[tot-1]p[tot]的右侧，出栈
				tot++;
				po[tot] = p[i];
			}

			for (int i = 0; i < tot; i++)ans += get_dis(po[i],po[i+1]);
			ans += get_dis(po[0],po[tot]);
			cout << int(ans + 0.5) << endl;
		}
	}
	return 0;
}