1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <map> 5 using namespace std; 6  7 const int maxn = 1005; 8 struct Node { 9     int id, x, y;10 }init[maxn], node[maxn], ans[maxn];11 12 13 int n, top;14 int G[maxn][maxn];15 int cross(Node n1, Node n2, Node n3) {16     return (n2.x - n1.x) * ( n3.y - n1.y ) - (n3.x - n1.x) * (n2.y - n1.y);17 }18 19 bool cmp(Node p1, Node p2) {20     if(p1.x != p2.x) {21         return p1.x < p2.x;22     }23     return p1.y < p2.y;24 }25 26 void conext() {27     sort(node + 1 + 1, node + n + 1, cmp);28     top = 0;29     ans[top++] = node[1];30     for(int i = 2; i <= n; i++) {31         while(top > 1 && cross(ans[top - 2], ans[top - 1], node[i]) <= 0 && G[ans[top-1].id][i]) {32             top--;33         } 34         ans[top++] = node[i];35     }36     int k = top;37     for(int i = n - 1; i >= 2; i--) {38         while(top > k && cross(ans[top - 2], ans[top - 1], node[i]) >= 0 && G[ans[top-1].id][i]) {39             top --;40         }41         ans[top++] = node[i];42     }43     if(top > 1) top--;44 }45 46 int main() {47     int n;48     while(EOF != scanf("%d",&n) ) {49         for(int i = 1; i <= n; i++) {50             scanf("%d %d %d",&init[i].id, &init[i].x, &init[i].y);51         }52         memset(G, 0, sizeof(G));53         for(int i = 1; i <= n i++) {54             for(int j = 1; j <= 4; j++) {55                 scanf("%d",&v);56                 G[i][v] = G[v][i] = 1;57             }58         }59         for(int i = 1; i <= n; i++) {60             for(int j = 0; j < n; j++) {61                 int x = ( i + j ) % n;62                 if(x == 0) x = n; 63                 node[x] = init[j + 1];64             }65             conext();66             for(int i = 0; i < top; i++) {67                 printf("%d ", ans[i].id);68             } puts("");69         }70     }71     return 0;72 }