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

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

问题链接:https://vjudge.net/problem/POJ-1696

Solution:

写的十分扎心的一题,改了好长时间,使用Graham Scan算法,求单个凸包复杂度\(O(nlogn)\),通过把丢弃的点重新利用再次求凸包的方法,最后将所有点遍历。

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

栈顶下面的一个元素→栈顶元素→新枚举的点

接着是第一个有变化的地方,通常我们求解凸包时,只在上面的旋向是逆时针的时候才保留栈顶元素,而这道题,为了走得距离最近,当三点共线的时候也保留栈顶元素,其余情况弹出栈顶,对应更新上面用到的两个栈中的点,使它们的含义与当前的栈的情况相符。另外一个不同的地方是,从栈顶丢掉的点现在我们不丢掉,而是存放到一个vector里,它们将用来求解下一次凸包。当我们求完一圈凸包后,我们将参照点置为当前栈顶元素,接着,在刚才抛弃的点集里重新进行极角排序,再次求解凸包,需要注意的是,这次就不能直接将前三个元素推到栈中了,而是直接接着已有的栈进行判断遍历每一个点,因为可能会遇到需要删除栈中点的情况,在下面的数据中,第一个n为14的就是例子。

#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