Advertisement
Guest User

Untitled

a guest
Feb 28th, 2015
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.65 KB | None | 0 0
  1. package main;
  2.  
  3. import geometry.Circle;
  4. import geometry.Point;
  5.  
  6. import java.io.File;
  7. import java.io.FileNotFoundException;
  8. import java.util.Arrays;
  9. import java.util.Scanner;
  10.  
  11. public class C {
  12. int n;
  13. double x[];
  14. double y[];
  15. double tmpY[];
  16. double tmpY2[];
  17.  
  18. static Scanner sc;
  19.  
  20. static {
  21. try {
  22. sc = new Scanner(new File("/home/nikola/storage/Competitions/Challenge24/2015/PROBLEMSET/input/C/4.in"));
  23. } catch (FileNotFoundException e) {
  24. // TODO Auto-generated catch block
  25. e.printStackTrace();
  26. }
  27. }
  28.  
  29. void solve() {
  30.  
  31. int tests = sc.nextInt();
  32.  
  33. while (tests-- > 0) {
  34. int n = sc.nextInt();
  35.  
  36. x = new double[n];
  37. y = new double[n];
  38.  
  39. for (int i = 0; i < n; i++) {
  40. x[i] = sc.nextDouble();
  41. }
  42.  
  43. for (int i = 0; i < n; i++) {
  44. y[i] = sc.nextDouble();
  45. }
  46.  
  47. Arrays.sort(x);
  48. Arrays.sort(y);
  49.  
  50. if (solve(n)) {
  51. System.out.println("YES");
  52. } else {
  53. System.out.println("NO");
  54. }
  55. }
  56. }
  57.  
  58. boolean solve(int n) {
  59.  
  60. tmpY = new double[n - 3];
  61. tmpY2 = new double[n - 3];
  62.  
  63. int asd = 150;
  64. for (int i1 = 0; i1 < n && asd > 0; i1++) {
  65. for (int i2 = i1 + 1; i2 < n && asd > 0; i2++) {
  66. for (int i3 = i2 + 1; i3 < n && asd > 0; i3++) {
  67. if (iste(i1, i2) && iste(i2, i3) && iste(i3, i1)) {
  68. continue;
  69. }
  70. asd--;
  71. for (int j1 = 0; j1 < n; j1++) {
  72. if (j1 > 0 && isteY(j1, j1 - 1)) continue;
  73. Point p1 = new Point(x[i1], y[j1]);
  74.  
  75. for (int j2 = 0; j2 < n; j2++) {
  76. if (j2 == j1) continue;
  77. if (j2 > 0 && isteY(j2, j2 - 1)) continue;
  78. Point p2 = new Point(x[i2], y[j2]);
  79. for (int j3 = 0; j3 < n; j3++) {
  80. if (j3 == j1 || j3 == j2) continue;
  81. if (j3 > 0 && isteY(j3, j3 - 1)) continue;
  82.  
  83. Point p3 = new Point(x[i3], y[j3]);
  84.  
  85. // Nadji centar
  86. Circle c = null;
  87. try {
  88. c = new Circle(p1, p2, p3);
  89. // System.out.println(p1);
  90. // System.out.println(p2);
  91. // System.out.println(p3);
  92. } catch (NullPointerException e) {
  93. asd++;
  94. continue;
  95. } catch (IllegalArgumentException e) {
  96. asd++;
  97. continue;
  98. }
  99.  
  100. int k = 0;
  101. for (int i = 0; i < n; i++) {
  102. if (i == j1 || i == j2 || i == j3) continue;
  103. if (y[i] > c.getCenter().getY()) {
  104. tmpY[k++] = 2 * c.getCenter().getY() - y[i];
  105. } else {
  106. tmpY[k++] = y[i];
  107. }
  108. }
  109.  
  110. boolean ccc = false;
  111.  
  112. k = 0;
  113. for (int i = 0; i < n; i++) {
  114. if (i == i1 || i == i2 || i == i3) {
  115. continue;
  116. }
  117.  
  118. double d = (c.getRadius() * c.getRadius() -
  119. Math.pow(x[i] - c.getCenter().getX(), 2.0));
  120.  
  121. if (d < 0) {
  122. ccc = true;
  123. break;
  124. }
  125.  
  126. double AA =
  127. Math.sqrt(d);
  128. tmpY2[k++] = c.getCenter().getY() - AA;
  129. }
  130.  
  131. if (ccc) continue;
  132.  
  133. Arrays.sort(tmpY);
  134. Arrays.sort(tmpY2);
  135.  
  136. boolean all = true;
  137. for (int i = 0; i < k; i++) {
  138. if (Math.abs(tmpY[i] - tmpY2[i]) > 1e-10) {
  139. all = false;
  140. }
  141. }
  142.  
  143. if (all) {
  144. return true;
  145. }
  146. }
  147. }
  148. }
  149. }
  150. }
  151. }
  152. return false;
  153. }
  154.  
  155. private boolean isteY(int i, int j) {
  156. return Math.abs(y[i] - y[j]) < 1e-10;
  157. }
  158.  
  159. private boolean iste(int i, int j) {
  160. return Math.abs(x[i] - x[j]) < 1e-10;
  161. }
  162.  
  163. public static void main(String[] args) {
  164. new C().solve();
  165. }
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement