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 }