Назад к лучшим решениям Status: AC, problem ZELC, contest ZEL07. By revenger (Denis Nazarov), 2007-02-23 09:40:54.
  1. #include <assert.h>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <iostream>
  6. #include <sstream>
  7. #include <cmath>
  8. #include <set>
  9.  
  10. #define maxn 3000
  11. #define maxm 7000
  12. #define DIST(u, v) ((x[u] - x[v]) * (x[u] - x[v]) + (y[u] - y[v]) * (y[u] - y[v]))
  13. #define POLAR(u, v) atan2(x[v] - x[u], y[v] - y[u])
  14. #define UPDATE(a, b, c, d) \
  15. 	       adj[d].clear(); \
  16. 	       adj[a].erase(b); adj[a].erase(c); adj[b].erase(a); adj[c].erase(a); \
  17.            adj[a].insert(d); adj[b].insert(d); adj[c].insert(d); \
  18. 		   adj[d].insert(a); adj[d].insert(b); adj[d].insert(c); \
  19. 		   //cout << a << " " << b << " " << c << " " << d << endl;
  20.  
  21. #define cos60 0.5
  22. #define sin60 0.8660254037844386
  23. #define pi 3.1415926535897932384
  24. #define eps 1e-5
  25. #define eps2 1e-6
  26.  
  27. using namespace std;
  28.  
  29. double x[maxm], y[maxm], best[maxn];
  30. int p[maxn], parent[maxn], n, m;
  31. set<int> adj[maxm];
  32.  
  33. struct adjVertex {
  34. 	int v;
  35. 	double phi;
  36.  
  37. 	adjVertex(int u0, int v) {
  38. 		this->v = v;
  39. 		this->phi = POLAR(u0, v);
  40. 	}
  41. };
  42.  
  43. bool operator<(const adjVertex& a, const adjVertex& b) {
  44. 	return a.phi > b.phi;
  45. }
  46.  
  47. bool steiner(int a, int b, int c, int d) {
  48. 	if (b == c || a == b || a == c || d >= 2 * n) return false;
  49.  
  50. 	double la = DIST(b, c);
  51. 	double lb = DIST(a, c);
  52. 	double lc = DIST(a, b);
  53.  
  54. 	if (la < eps2 || lb < eps2 || lc < eps2) return false;
  55.  
  56. 	double cosa = (lb + lc - la) / 2.0 / sqrt(lb) / sqrt(lc);
  57. 	double cosb = (la + lc - lb) / 2.0 / sqrt(la) / sqrt(lc);
  58. 	double cosc = (la + lb - lc) / 2.0 / sqrt(la) / sqrt(lb);
  59. 	if (cosa < eps - 0.5 || cosb < eps - 0.5 || cosc < eps - 0.5) return false;
  60.  
  61. 	if (cosb < cosc && cosb < cosa) return steiner(b, a, c, d);
  62. 	if (cosc < cosb && cosc < cosa) return steiner(c, a, b, d);
  63.  
  64. 	double dx = x[b] - x[c];
  65. 	double dy = y[b] - y[c];	
  66. 	x[d + 1] =  dx * cos60 + dy * sin60 + x[c];
  67. 	y[d + 1] = -dx * sin60 + dy * cos60 + y[c];
  68. 	x[d + 2] =  dx * cos60 - dy * sin60 + x[c];
  69. 	y[d + 2] =  dx * sin60 + dy * cos60 + y[c];
  70.  
  71. 	int D = DIST(d + 1, a) > DIST(d + 2, a) ? d + 1 : d + 2;
  72. 	
  73. 	double ld = DIST(a, D);
  74. 	double cose = (lb + ld - la) / 2.0 / sqrt(lb) / sqrt(ld);
  75. 	double sine = sqrt(1 - cose * cose);
  76. 	double phie = acos(cose);
  77. 	double phif = pi / 3.0 - phie;
  78. 	double lle = sqrt(lb) * sine / sin60;
  79. 	
  80. 	double cosf = cos(phif);
  81. 	double sinf = sin(phif);
  82.  
  83. 	dx = (x[a] - x[c]) / sqrt(lb) * lle;
  84. 	dy = (y[a] - y[c]) / sqrt(lb) * lle;	
  85. 	x[d + 1] =  dx * cosf + dy * sinf + x[c];
  86. 	y[d + 1] = -dx * sinf + dy * cosf + y[c];
  87. 	x[d + 2] =  dx * cosf - dy * sinf + x[c];
  88. 	y[d + 2] =  dx * sinf + dy * cosf + y[c];
  89.  
  90. 	D = DIST(d + 1, b) < DIST(d + 2, b) ? d + 1 : d + 2;
  91. 	
  92. 	x[d] = x[D];
  93. 	y[d] = y[D];
  94.  
  95. 	return (x[d] > -1e6 && x[d] < 1e6 && y[d] > -1e6 && y[d] < 1e6);
  96. }
  97.  
  98. void greedy() {
  99. 	int i, j, current, first, k;
  100. 	m = 0;
  101.  
  102. 	for (i = 0; i < n; i++) if (adj[i].size() > 1) {
  103. 		vector<adjVertex> adjv;
  104. 		for (set<int>::iterator it = adj[i].begin(); it != adj[i].end(); it++) adjv.push_back(adjVertex(i, *it));
  105. 		sort(adjv.begin(), adjv.end());
  106.  
  107. 		current = adjv[0].v;
  108. 		first = current;
  109.  
  110. 		bool failed = false;
  111. 		for (j = 1; j < adjv.size(); j++)
  112. 			if (steiner(i, current, adjv[j].v, n + m)) {
  113. 				UPDATE(i, current, adjv[j].v, n + m)
  114. 				current = n + m;
  115. 				if (!failed) first = current;
  116. 				m += 1;
  117. 			} else {
  118. 				current = adjv[j].v;
  119. 				failed = true;
  120. 			}
  121.  
  122. 		if (steiner(i, first, current, n + m)) {
  123. 			UPDATE(i, first, current, n + m)
  124. 			m += 1;
  125. 		}
  126. 	}
  127. }
  128.  
  129. int main() {
  130. 	/*freopen("zelc.in", "rt", stdin);
  131. 	freopen("zelc.out", "wt", stdout);*/
  132.  
  133. 	srand(30051985);
  134.  
  135. 	int testCount, i, j, k, lim, v0;
  136. 	scanf("%d", &testCount);
  137. 	
  138. 	while (testCount--) {
  139. 		scanf("%d", &n);
  140. 		v0 = 1;
  141. 		for (i = 0; i < n; i++)	scanf("%lf %lf", &x[i], &y[i]);
  142. 		for (i = 0; i < n; i++) {
  143. 			best[i] = DIST(v0, i);
  144. 			p[i] = i < v0 ? i : i + 1;
  145. 			parent[i] = v0;
  146. 		}
  147. 		for (lim = n - 1, i = 1; i < n; i++) {
  148. 			for (k = 0, j = 0; j < lim; j++) if (best[p[k]] > best[p[j]]) k = j;
  149. 			m = p[k];
  150. 			p[k] = p[--lim];
  151. 			for (j = 0; j < lim; j++) {
  152. 				double dist = DIST(m, p[j]);
  153. 				if (best[p[j]] > dist) { 
  154. 					best[p[j]] = dist; 
  155. 					parent[p[j]] = m; 
  156. 				}
  157. 			}
  158. 		}
  159.  
  160. 		for (i = 0; i < n; i++) adj[i].clear();
  161. 		for (i = 0; i < n; i++) if (i != v0) {
  162. 			adj[i].insert(parent[i]);
  163. 			adj[parent[i]].insert(i);
  164. 		}
  165.  
  166. 		greedy();
  167.  
  168. 		printf("%d\n", m);
  169. 		for (i = n; i < n + m; i++) printf("%lf %lf\n", x[i], y[i]);
  170. 		printf("%d\n", n + m - 1);
  171. 		for (j = 0, i = 0; i < n + m; i++) {
  172. 			for (set<int>::iterator it = adj[i].begin(); it != adj[i].end(); it++) {
  173. 				int vertex = *it;
  174. 				if (vertex > i) { printf("%d %d\n", i, vertex); j++; };
  175. 			}			
  176. 		}
  177. 	}
  178. }