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;
}