[POJ 1696] Space Ants
[题目大意]
给定多个点, 对他们按照下面的规则排序, 每个都在前一个点组成的左边, 并且连线不相交 (典型如图)
[题目分析]
不断进行极角排序, 不断选取一定区域内最符合要求的解
[代码]
- #include<cstdio>
- #include<iostream>
- #include<algorithm>
- #define ll double
- using namespace std;
- const double eps = 1e-9;
- const int MAXN = 1010;
- int sgn(ll x)
- {
- if (x> eps) return 1;
- if (x <-eps)return -1;
- return 0;
- }
- struct P
- {
- ll x, y ;
- int index;
- P() {};
- P(double a, double b) :x(a), y(b) {}
- P operator -(P a) { return P(x - a.x, y - a.y); }
- double operator *(P a) { return x * a.x + y * a.y ; }
- double operator ^(P a) { return x * a.y - y * a.x ; }
- };
- struct L
- {
- P s, t;
- L() {}
- L(P a, P b) :s(a), t(b) {}
- };
- double dis(P a, P b)
- {
- return (b - a)*(b - a);
- }
- P p[MAXN];
- int pos;
- bool cmp(P a, P b)
- {
- int tmp = sgn((a - p[pos]) ^ (b - p[pos]));
- if (tmp == 0) return dis(b, p[pos])> dis(a, p[pos]);
- if (tmp < 0) return false;
- return true;
- }
- int main()
- {
- int T;
- scanf("%d", &T);
- while (T--)
- {
- int n;
- scanf("%d", &n);
- for (int i = 1; i <= n; i++)
- {
- scanf("%d %lf %lf", &p[i].index, &p[i].x, &p[i].y);
- if ((p[i].y == p[1].y && p[i].x < p[1].x )||(p[i].y<p[1].y))
- swap(p[1], p[i]);
- }
- pos = 1;
- for (int i = 2; i <= n; i++)
- {
- sort(p+i,p+n+1,cmp);
- pos++;
- }
- printf("%d", n);
- for (int i = 1; i <= n; i++)
- {
- printf("%d", p[i].index);
- if (i != n)
- printf(" ");
- else
- printf("\n");
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3229626.html