## 【POJ-1696】Space Ant【Graham Scan + polar angle sorting】

【POJ-1696】Space Ant【Graham Scan + polar angle sorting】

Solution:

Graham Scan算法大体思路是首先找到最下方的点，之后以这个点为参照将所有点按照极角进行排序【实际上，由于不便于求解角度，我们使用判断三点围成矢量三角的旋转方向的方法来判断两个点那个点的极角更小，使用这种方法将不考虑极角的正负，所以即便我们选取的点不是最下方的点也会将所有的点从最下方的点开始排序，前提是，选作参照的点不能是四周都有点的，同时应当保证这个点在所求凸包上】，当两个点具有相同的极角时，我们按照距离从近到远进行排序。排好序后，我们首先把前三个点加入到栈中，接着从第四个点开始遍历，不断用下面这三个点判断旋向：

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int LIM = 50 + 10;
struct Point {
int x, y, id;
Point operator - (const Point &p) const {
Point ret = {x - p.x, y - p.y};
return ret;
}
int operator ^ (const Point &p) const {
return x * p.y - y * p.x;
}
} ps[LIM];
int n;
Point bottom;
enum {CLOCK = -1, COL, CONTER};
int getOrientation(const Point &a, const Point &b, const Point &c) {
Point v1 = b - a;
Point v2 = c - a;
int res = v1 ^ v2;
if (res < 0) return CLOCK;
else if (res == 0) return COL;
else return CONTER;
}
int distSq(const Point &a, const Point &b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmp(const Point &a, const Point &b) {
int o = getOrientation(bottom, a, b);
if (o == COL)
return distSq(a, bottom) <= distSq(b, bottom);
return o == CONTER;
}

stack<Point> s;
void GramahScan() {
if (n <= 3) {
for (int i = 1; i <= n; i++)
s.push(ps[i]);
return;
}
bottom = ps[1];
vector<Point> full, unduplicated, dup;
full.push_back(ps[1]);
/* Find the bottom point */
for (int i = 2; i <= n; i++) {
full.push_back(ps[i]);
if (ps[i].y < bottom.y) bottom = ps[i];
}
#ifdef DBG
/* Show the bottom */
printf("At %d: id = %d: %d, %d\n", __LINE__, bottom.id, bottom.x, bottom.y);
#endif
/* polar angle sorting using bottom point */
sort(full.begin(), full.end(), cmp);
#ifdef DBG
/* Show the full after sort */
printf("After sorting...\n");
for (int i = 0; i < full.size(); i++)
printf("At %d: id = %d: %d, %d\n", __LINE__, full[i].id, full[i].x, full[i].y);
#endif
for (int i = 0; i < full.size(); i++) {
unduplicated.push_back(full[i]);
}
Point top;
Point nexttop;
/* 最初插入三个 */
s.push(unduplicated[0]);
s.push(unduplicated[1]);
s.push(unduplicated[2]);
unduplicated.erase(unduplicated.begin());
unduplicated.erase(unduplicated.begin());
unduplicated.erase(unduplicated.begin());
while (unduplicated.size() > 1) {
#ifdef DBG
printf("__usize: %d__\n", unduplicated.size());
#endif
for (int i = 0; i < unduplicated.size(); i++) {
top = s.top();
s.pop();
nexttop = s.top();
while (getOrientation(nexttop, top, unduplicated[i]) != CONTER) {
s.pop();
dup.push_back(top);
#ifdef DBG
printf("Note, at %d, we remove %d\n", __LINE__, top.id);
printf("Note, at %d, new top is %d\n", __LINE__, nexttop.id);
#endif
top = nexttop;
nexttop = s.top();
}
s.push(top);
s.push(unduplicated[i]);
#ifdef DBG
printf("Ok, at %d, we add %d\n", __LINE__, unduplicated[i].id);
#endif
}
full = dup;
#ifdef DBG
printf("At %d - full size: %d\n", __LINE__, full.size());
#endif
unduplicated.clear();
dup.clear();
bottom = s.top();
#ifdef DBG
printf("At %d - bottom id - %d: %d, %d\n", __LINE__, bottom.id, bottom.x, bottom.y);
#endif
sort(full.begin(), full.end(), cmp);
#ifdef DBG
/* Show the full after sort */
printf("After sorting...\n");
for (int i = 0; i < full.size(); i++)
printf("At %d: id = %d: %d, %d\n", __LINE__, full[i].id, full[i].x, full[i].y);
#endif
for (int i = 0; i < full.size(); i++) {
unduplicated.push_back(full[i]);
}
#ifdef DBG
printf("At %d: dup size = %d\n", __LINE__, dup.size());
#endif
}
if (unduplicated.size()) s.push(unduplicated[0]);
}

void showAns() {
Point crt = s.top();
s.pop();
if (!s.empty()) showAns();
printf(" %d", crt.id);
}

int main(void) {
int m;
scanf("%d", &m);
while (m--) {
while (!s.empty()) s.pop();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &ps[i].id, &ps[i].x, &ps[i].y);
}
#ifdef DBG
printf("Show all\n");
for (int i = 1; i <= n; i++)
printf("At %d: id = %d: %d, %d\n", __LINE__, ps[i].id, ps[i].x, ps[i].y);
#endif
GramahScan();
printf("%d", s.size());
showAns();
putchar('\n');
}
return 0;
}

3
14
1 	55 	24
2 	86 	18
3 	49 	39
4 	62 	5
5 	72 	84
6 	69 	49
7 	72 	99
8 	71 	34
9 	57 	37
10 	6 	48
11 	92 	43
12 	98 	4
13 	80 	69
14 	33 	88
28
1 	47 	25
2 	47 	56
3 	7 	44
4 	98 	15
5 	14 	94
6 	29 	5
7 	90 	94
8 	90 	20
9 	34 	30
10 	14 	39
11 	77 	56
12 	92 	71
13 	26 	59
14 	7 	33
15 	98 	8
16 	99 	65
17 	3 	57
18 	89 	11
19 	24 	94
20 	26 	48
21 	63 	8
22 	64 	70
23 	24 	46
24 	34 	51
25 	100 	31
26 	82 	22
27 	60 	60
28 	55 	59
12
1 	25 	28
2 	56 	16
3 	93 	41
4 	18 	5
5 	46 	38
6 	19 	39
7 	7 	64
8 	12 	92
9 	37 	69
10 	74 	46
11 	19 	71
12 	87 	63