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 += ' '; 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 }
GYN托我很久了 昨晚正式帮他写好了
也算是第一次帮写项目了哈哈哈