JAG pI - Color the Map Extreme

亂做一通
35個點就亂著色啦XD
(幾何part由西瓜提供XD)

1. #include<cstdio>
2. #include<cstdlib>
3. #include<algorithm>
4. #include<cstring>
5. #include<vector>
6. #include<utility>
7. #include<map>
8. #include<set>
9. #include<queue>
10. #include<cmath>
11. #define X first
12. #define Y second
13. using namespace std;
14. typedef long long int int64;
15. typedef pair<int,int> pii;
16. pii operator-(const pii &a, const pii &b){
17. return pii(a.X - b.X, a.Y - b.Y);
18. }
19.  
20. inline int dot(pii p1, pii p2){
21. return p1.X * p2.X + p1.Y * p2.Y;
22. }
23. inline int cross(pii p1, pii p2){
24. return p1.X * p2.Y - p2.X * p1.Y;
25. }
26.  
27. bool check(pii p1, pii p2, pii p3, pii p4){
28. if((p1 == p3) and (p2 == p4)) return true;
29. if((p1 == p4) and (p2 == p3)) return true;
30. if ((p2.Y - p1.Y) * (p4.X - p3.X) != (p4.Y - p3.Y) * (p2.X - p1.X)) return false;
31. if (cross(p2 - p1, p3 - p1)) return false;
32. if (dot(p1 - p3, p1 - p4) < 0 || dot(p2 - p3, p2 - p4) < 0 ||
33. dot(p3 - p1, p3 - p2) < 0 || dot(p4 - p1, p4 - p2) < 0)
34. return true;
35. return false;
36. }
37. vector<int> to[100];
38. int col[100];
39. void color(int prc){
40. //printf("draw at %d\n", prc);
41. int ctab[5] = {0};
42. for(int lx = 0;lx < to[prc].size();lx++){
43. int pind = to[prc][lx];
44. if(col[pind] != -1)
45. ctab[col[pind]] = 1;
46. }
47. int get_color = 4;
48. for(int lx = 1;lx <= 4;lx++){
49. if(ctab[lx] == 0){
50. get_color = lx;
51. break;
52. }
53. }
54. col[prc] = get_color;
55. //printf("draw %d\n", get_color);
56. int a[100];
57. for(int lx = 0;lx < to[prc].size();lx++){ a[lx] = lx; }
58. random_shuffle(a, a+to[prc].size());
59. for(int ly = 0;ly < to[prc].size();ly++){
60. int pind = to[prc][a[ly]];
61. if(col[pind] != -1) continue;
62. color(pind);
63. }
64. return;
65. }
66. int main()
67. {
68. int n;
69. srand(514514);
70. for(;;){
71. scanf("%d", &n);
72. if(n == 0) break;
73. pii polys[100][100];
74. int ptcnt[100] = {0};
75. bool metr[100][100] = {0};
76. for(int lx = 0;lx < n;lx++)
77. to[lx].clear();
78. for(int lx = 0;lx < n;lx++){
79. scanf("%d", ptcnt+lx);
80. for(int ly = 0;ly < ptcnt[lx];ly++)
81. scanf("%d %d", &polys[lx][ly].X, &polys[lx][ly].Y);
82. }
83. for(int lx = 0;lx < n;lx++){
84. for(int ly = lx+1;ly < n;ly++){
85. //printf("cal %d -> %d\n", lx, ly);
86. bool ok = false;
87. for(int la = 0;la < ptcnt[lx] and not ok; la++){
88. for(int lb = 0;lb < ptcnt[ly] and not ok;lb++){
89. int na = (la+1)%ptcnt[lx];
90. int nb = (lb+1)%ptcnt[ly];
91. if(check(polys[lx][la], polys[lx][na], polys[ly][lb], polys[ly][nb])){
92. //printf("%d %d %d %d\n", la, lb, na, nb);
93. ok = true;
94. }
95. }
96. }
97. metr[lx][ly] = ok;
98. metr[ly][lx] = ok;
99. }
100. }
101. if(n == 1){ puts("1"); continue; }
102.  
103. for(int lx = 0;lx < n;lx++)
104. for(int ly = 0;ly < n;ly++)
105. if(metr[lx][ly]){
106. //printf("%d -> %d\n", lx, ly);
107. to[lx].push_back(ly);
108. }
109. int min_color = 4;
110. for(int _ = 0;_ < 1000;_++){
111. for(int lx = 0;lx < n;lx++) col[lx] = -1;
112. for(int lx = 0;lx < n;lx++)
113. if(col[lx] == -1)
114. color(lx);
115. int max_c = -1;
116. for(int lx = 0;lx < n;lx++) max_c = max(max_c, col[lx]);
117. min_color = min(min_color, max_c);
118. }
119. if(min_color == 4){
120. // check 3-cyc
121. int cyc3 = 0;
122. for(int lx = 0;lx < n;lx++)
123. for(int ly = lx+1;ly < n;ly++)
124. for(int lz = ly+1;lz < n;lz++)
125. cyc3 += metr[lx][ly] and metr[lz][ly] and metr[lx][lz];
126. if(cyc3 == 0){puts("3"); continue;}
127. }
128. printf("%d\n", min_color);
129. }
130. return 0;
131. }