poj1696

题意：给定一些点，找一条路径，要求经过点最多，并且不能相交。。。

思路：可以用极角排序，但是实际上就是凸包的变形。。套用凸包模板即可。。

code：

 1 /*
 2   Time:2013-03-26 18:22:16
 3   State:Accepted
 4 */
 5 #include<iostream>
 6 #include<cstring>
 7 #include<cstdlib>
 8 #include<cmath>
 9 #include<algorithm>
10 #include<cstdio>
11 #include<string>
12 using namespace std;
13 struct oo{int x , y , p;};
14 int M,n;
15 oo a[1500], pa;
16 
17 void init(){
18      scanf("%d", &n );
19      for (int i = 0; i < n; ++i)
20            scanf("%d%d%d",&a[i].p, &a[i].x , &a[i].y);
21 }
22 
23 bool cmp(const oo a, const oo b){
24      if (a.y < b.y || a.y == b.y && a.x < b.x) return true;
25      return false;
26 }
27 
28 bool cmpx(const oo a, const oo b){
29     int x1 = a.x - pa.x;
30     int x2 = b.x - pa.x;
31     int y1 = a.y - pa.y;
32     int y2 = b.y - pa.y;
33     if (x1*y2 -x2*y1 >0) return 1;
34     if (x1*y2 - x2*y1 == 0 && 
35     x1*x1 + y1*y1 < x2*x2 + y2* y2) return 1;
36     return 0;
37 }
38 
39 void solve(){
40      sort(a, a + n, cmp);  
41      for (int i = 0; i < n - 1; ++i){
42          pa = a[i];
43          sort(a + i + 1, a + n, cmpx );
44      }
45      printf("%d ", n);
46      for (int i = 0;  i < n; ++i)
47           printf("%d ",a[i].p);
48     
49  printf("\n");
50 }
51 
52 int main(){
53     freopen("poj1696.in","r", stdin);
54     freopen("poj1696.out","w",stdout);
55     scanf("%d",&M);
56     while (M--){
57        init();
58        solve();
59     }
60     fclose(stdin); fclose(stdout);
61 }