Advertisement
Guest User

Untitled

a guest
Feb 28th, 2015
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.32 KB | None | 0 0
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cmath>
  4. #include<algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int N = 1000;
  9. double eps = 1e-8;
  10. double x[N];
  11. double y[N];
  12. double x_dbl[N];
  13. double y_dbl[N];
  14. bool y_marked[N];
  15. int n;
  16.  
  17. void build_line(double x1, double y1, double x2, double y2, double& A, double& B, double& C)
  18. {
  19. A = y1 - y2;
  20. B = x2 - x1;
  21. C = x1*y2 - x2*y1;
  22. }
  23.  
  24. void build_circ(double x1, double x2, double x3, double y1, double y2, double y3, double& x0, double& y0, double& r)
  25. {
  26. double A1, B1, C1;
  27. build_line(x1, y1, x2, y2, A1, B1, C1);
  28. double A2, B2, C2;
  29. build_line(x1, y1, x3, y3, A2, B2, C2);
  30. double A3, B3, C3;
  31. double A4, B4, C4;
  32. if (A1 == 0)
  33. {
  34. A1 = 1;
  35. B1 = 0;
  36. }
  37. if (B1 == 0)
  38. {
  39. A1 = 0;
  40. B1 = 1;
  41. }
  42. if (B2 == 0)
  43. {
  44. B2 = 1;
  45. A2 = 0;
  46. }
  47. if (A2 == 0)
  48. {
  49. A2 = 1;
  50. B2 = 0;
  51. }
  52. build_line((x1 + x2)/2, (y1 + y2)/2, (x1 + x2)/2 + A1, (y1 + y2)/2 + B1, A3, B3, C3);
  53. build_line((x1 + x3)/2, (y1 + y3)/2, (x1 + x3)/2 + A2, (y1 + y3)/2 + B2, A4, B4, C4);
  54. if (abs(A3*B4 - A4*B3) < eps)
  55. {
  56. x0 = 0; y0 = 0; r = -1;
  57. }
  58. else
  59. {
  60. x0 = (B3*C4 - B4*C3)/(A3*B4 - A4*B3);
  61. y0 = (C3*A4 - C4*A3)/(A3*B4 - A4*B3);
  62. r = (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0);
  63. }
  64. }
  65.  
  66.  
  67. bool go(double x1, double x2, double x3, double y1, double y2, double y3, double* x, double* y)
  68. {
  69. double r, y0, x0;
  70. build_circ(x1, x2, x3, y1, y2, y3, x0, y0, r);
  71. if (r == -1)
  72. return false;
  73. for (int i = 0; i < n; i++)
  74. {
  75. if ((x[i] - x0)*(x[i] - x0) > r)
  76. {
  77. return false;
  78. }
  79. double yy = r - (x[i] - x0)*(x[i] - x0);
  80. bool can = 0;
  81. for (int j = 0; (j < n) && (!can); j++)
  82. {
  83. can = 0;
  84. if (abs((y[j] - y0)*(y[j] - y0) - yy) < eps && y_marked[j] == 0)
  85. {
  86. can = 1;
  87. y_marked[j] = 1;
  88. }
  89. }
  90. if (!can)
  91. return false;
  92. }
  93. return true;
  94. }
  95.  
  96. int main()
  97. {
  98. freopen("5.in" ,"r", stdin);
  99. freopen("5_2.out", "w", stdout);
  100.  
  101. int t;
  102. cin >> t;
  103. for (int i = 0; i < t; i++)
  104. {
  105. cin >> n;
  106.  
  107. for (int j = 0; j < n; j++)
  108. {
  109. cin >> x[j];
  110. x_dbl[j] = x[j];
  111. }
  112. for (int j = 0; j < n; j++)
  113. {
  114. cin >> y[j];
  115. y_dbl[j] = y[j];
  116. }
  117. sort(x, x + n);
  118. sort(y, y + n);
  119. int mx = unique(x_dbl, x_dbl + n) - x_dbl;
  120. int my = unique(y_dbl, y_dbl + n) - y_dbl;
  121. if (mx >= 3)
  122. {
  123. bool ans = false;
  124. for (int i1 = 0; i1 < n; i1++)
  125.  
  126. for (int i2 = 0; i2 < n; i2++)
  127. {
  128. if (i1 == i2) continue;
  129. for (int i3 = 0; i3 < n; i3++)
  130. {
  131. if (i3 == i1 || i3 == i2) continue;
  132. for (int j = 0; j < n; j++)
  133. y_marked[j] = 0;
  134. ans |= go(x_dbl[0], x_dbl[1], x_dbl[2], y[i1], y[i2], y[i3], x, y);
  135. }
  136. }
  137. if (ans)
  138. {
  139. cout << "YES" << endl;
  140. continue;
  141. }
  142. }
  143. else if (my >= 3)
  144. {
  145. bool ans = false;
  146. for (int i1 = 0; i1 < n; i1++)
  147. {
  148. for (int i2 = 0; i2 < n; i2++)
  149. {
  150. if (i1 == i2) continue;
  151. for (int i3 = 0; i3 < n; i3++)
  152. {
  153. for (int j = 0; j < n; j++)
  154. y_marked[j] = 0;
  155. if (i3 == i1 || i3 == i2) continue;
  156. ans |= go(y_dbl[0], y_dbl[1], y_dbl[2], x[i1], x[i2], x[i3], y, x);
  157. }
  158. }
  159. }
  160. if (ans)
  161. {
  162. cout << "YES" << endl;
  163. continue;
  164. }
  165. }
  166. else
  167. {
  168. cout << "abacaba" << endl;
  169. continue;
  170. }
  171. cout << "NO" << endl;
  172.  
  173. }
  174.  
  175. return 0;
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement