POJ1696 (Space Ant)[计算几何]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=1696

这题比较容易想到贪心策略：每次只找当前结点需要向逆时针转最小角度能到达的点即可。每次拓展一个点之后以当前结点为基准对其它点进行极角排序，并找到第一个从当前结点旋转方向为逆时针并没被访问过的点拓展即可。

但有一个坑点：极角排序时如果当前基准点位于许多点中间而非它们的边界上，那么极角序并不是唯一的（极角序转过360度依次减小形成了一个环），此时排序的结果是不可用的，因此要在排序前去掉所有在当前结点（准确地说是当前边）顺时针方向的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-8;
const double inf=1e20;
const int maxn=109;
const int maxp=59;
int sgn(double x) {
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    else return 1;
}
inline double sqr(double x) { return x*x; }

struct Point {
    double x,y;
    int index;
    Point() {}
    Point(double _x,double _y,int _index=0) {
        x=_x;
        y=_y;
        index=_index;
    }
    double operator ^(const Point &b) const {
        return x*b.y-y*b.x;
    }
    Point operator -(const Point &b) const {
        return Point(x-b.x,y-b.y);
    }
    bool operator ==(Point b) const {
        return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
    }
    double operator *(const Point& b) const {
        return x*b.x+y*b.y;
    }
    double distance(Point p) {
        return hypot(x-p.x,y-p.y);
    }
    bool operator <(Point b) const {
        return sgn(x-b.x)==0 ? sgn(y-b.y)<0 : x<b.x;
    }
};
struct polygon {
    int n,n2;
    Point p[maxp];
    bool vis[maxp];
    int seq[maxp],t;
    void init() {
        n=0;
        t=0;
        memset(vis,0,sizeof(vis));
    }
    void add(Point q) {
        p[n++]=q;
    }
    struct cmp {
        Point p;
        cmp(const Point &p0) { p=p0; }
        bool operator() (const Point &aa,const Point &bb) {
            Point a=aa,b=bb;
            int d=sgn((a-p)^(b-p));
            if(d==0) {
                return sgn(a.distance(p)-b.distance(p)) < 0;
            }
            return d>0;
        }
    };
    void norm(Point start,Point lim) {
        for(int i=0;i<n;i++) {
            if(vis[p[i].index] || sgn(lim^(p[i]-start))<0) swap(p[i],p[n-1]),n--;
        }
        sort(p,p+n,cmp(start));
    }
    void solve() {
        Point start=Point(200,200);
        Point lim=Point(1,0);
        for(int i=0;i<n;i++) {
            if(!(sgn(start.y-p[i].y)==0 ? sgn(start.x-p[i].x)<0 : start.y<p[i].y)) {
                start=p[i];
            }
        }
        vis[start.index]=true;
        seq[t++]=start.index;
        Point nex;
        while(true) {
            norm(start,lim);
            bool flag=0;
            for(int i=0;i<n;i++) {
                if(!vis[p[i].index] && sgn(lim^(p[i]-start))>=0) {
                    flag=1;
                    nex=p[i];
                    vis[p[i].index]=1;
                    seq[t++]=p[i].index;
                    lim=nex-start;
                    start=nex;
                    break;
                }
            }
            if(!flag) break;
        }
        printf("%d ",t);
        for(int i=0;i<t;i++) printf(i==t-1? "%d" :"%d ",seq[i]);
        printf("\n");
    }
}poly;
int main() {
    int T;
    int n;
    int index,x,y;
    int miy;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        poly.init();
        for(int i=0;i<n;i++) {
            scanf("%d%d%d",&index,&x,&y);
            poly.add(Point(x,y,index));
        }
        poly.solve();
    }
}