1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <vector>  6 #include <cmath>  7 #include <map>  8 using namespace std;  9 const int maxn = 1010;//点的个数  可以修改  maxn <= 20005即可满足要求 10 const double pi = 3.141592653589; 11 struct Point { 12     int id; 13     int x; 14     int y; 15 }; 16 bool cmp(Point p1, Point p2) { 17     if(p1.id != p2.id) return p1.id < p2.id; 18 } 19  20 class Loop { 21 public: 22     int n; 23     int G[maxn][maxn]; 24     vector<int> V[maxn]; 25     Point init[maxn], point[maxn], ans[maxn]; 26     map<string, int> mp; 27  28     void Init(int n) { 29         this -> n = n; 30         for(int i = 1; i <= n; i++) { 31             V[i].clear(); 32         } 33         mp.clear(); 34         memset(G, 0, sizeof(G)); 35     } 36  37     void input() { 38         for(int i = 1; i <= n; i++) { 39             scanf("%d %d %d",&init[i].id, &init[i].x, &init[i].y); 40         } 41         int u, v; 42         for(int i = 1; i <= n; i++) { 43             scanf("%d",&u); 44             for(int j = 1; j <= 4; j++) { 45                 scanf("%d",&v); 46                 if(v != 0) { 47                     G[u][v] = G[v][u] = 1; 48                     V[u].push_back(v); 49                 } 50             } 51         } 52     } 53  54     void check(Point a[maxn], int cnt) { 55         if(cnt < 3) return ; 56         Point b[maxn]; 57         for(int i = 0; i < cnt; i++) { 58             b[i] = a[i]; 59         } 60         sort(b, b + cnt, cmp); 61         string s; 62         for(int i = 0; i < cnt; i++) { 63             char str[10]; 64             sprintf(str, "%d", b[i].id); 65             s += str; 66         } 67         s += ‘\0‘; 68         if(!mp[s]) { 69             mp[s] = 1; 70             for(int i = 0; i < cnt; i++) { 71                 printf("%d ", a[i].id); 72             } puts(""); 73         } 74     } 75  76     double C(Point p0, Point p1, Point p2) { 77         double x1 = p1.x - p0.x; double y1 = p1.y - p0.y; 78         double x2 = p2.x - p0.x; double y2 = p2.y - p0.y; 79         double a = sqrt( x1*x1 + y1*y1 ); 80         double b = sqrt( x2*x2 + y2*y2 ); 81         double ab = x1*x2 + y1*y2; 82         double caob = ab / ( a * b ); 83         double jiaodu = acos(caob); 84         return jiaodu / pi * 180 + 1e-6; 85     } 86     double D(Point p0, Point p1, Point p2) { 87         double x1 = p1.x - p0.x; double y1 = p1.y - p0.y; 88         double x2 = p2.x - p0.x; double y2 = p2.y - p0.y; 89         double ans = x1 * y2 - x2 * y1; 90         return ans; 91     } 92     int eps(double x) { 93         if(fabs(x) < 1e-8) return 0; 94         if(x < 0) return -1; 95         return 1; 96     } 97  98     void solve() { 99         for(int i = 1; i <= n; i++) {100             for(int j = 1; j <= n; j++) {101                 if(i == j) continue;102                 if(!G[i][j]) continue;103                 int vis[maxn] = { 0 };104                 int cnt = 1;105                 vis[i] = vis[j] = 1;106                 point[cnt++] = init[i];107                 point[cnt++] = init[j];108                 int num = n - 2;109                 while(num--) {110                     double ang = 181;111                     int id_num = n + 1;112                     int now = point[cnt - 1].id;113                     bool fla = false;114                     for(int k = 0; k < V[now].size(); k++) {115                         int u = V[now][k];116                         if(vis[u]) continue;117                         double a1 = D(point[cnt - 1], point[cnt - 2], init[u]);118                         if(eps(a1) >= 0) {119                             double a2 = C(point[cnt - 1], point[cnt - 2], init[u]);120                             if(ang > a2) {121                                 ang = a2;122                                 id_num = u;123                             }124                         }125                     }126                     if(id_num <= n) {127                         fla = true;128                         point[cnt++] = init[id_num];129                         vis[id_num] = 1;130                     } else {131                         double ang2 = -1;132                         int id_num2 = n + 1;133                         for(int k = 0; k < V[now].size(); k++) {134                             int u = V[now][k];135                             if(vis[u]) continue;136                             double a1 = D(point[cnt - 1], point[cnt - 2], init[u]);137                             if(eps(a1) < 0) {138                                 double a2 = C(point[cnt - 1], point[cnt - 2], init[u]);139                                 if(ang < a2) {140                                     ang2 = a2;141                                     id_num2 = u;142                                 }143                             }144                         }145                         if(id_num2 <= n) {146                             fla = true;147                             point[cnt++] = init[id_num2];148                             vis[id_num2] = 1;149                         }150                     }151                     if(!fla) break;152                     bool flag = false;153                     for(int l = cnt - 3; l >= 1; l--) {154                         if(G[point[l].id][id_num]) {155                             flag = true;156                             int cnt_1 = 0;157                             for(int ll = l; ll < cnt; ll++) {158                                 ans[cnt_1++] = point[ll];159                             }160                             check(ans, cnt_1);161                             break;162                         }163                     }164                     if(flag) {165                         break;166                     }167                 }168             }169         }170     }171 };172 Loop l1;173 174 int main() {175     int n;176     freopen("in.txt","r",stdin);177     while(EOF != scanf("%d",&n) ) {178         l1.Init(n);179         l1.input();180         l1.solve();181     }182     return 0;183 }