Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main;
- import geometry.Circle;
- import geometry.Point;
- import java.io.File;
- import java.io.FileNotFoundException;
- import java.util.Arrays;
- import java.util.Scanner;
- public class C {
- int n;
- double x[];
- double y[];
- double tmpY[];
- double tmpY2[];
- static Scanner sc;
- static {
- try {
- sc = new Scanner(new File("/home/nikola/storage/Competitions/Challenge24/2015/PROBLEMSET/input/C/4.in"));
- } catch (FileNotFoundException e) {
- // TODO Auto-generated catch block
- e.printStackTrace();
- }
- }
- void solve() {
- int tests = sc.nextInt();
- while (tests-- > 0) {
- int n = sc.nextInt();
- x = new double[n];
- y = new double[n];
- for (int i = 0; i < n; i++) {
- x[i] = sc.nextDouble();
- }
- for (int i = 0; i < n; i++) {
- y[i] = sc.nextDouble();
- }
- Arrays.sort(x);
- Arrays.sort(y);
- if (solve(n)) {
- System.out.println("YES");
- } else {
- System.out.println("NO");
- }
- }
- }
- boolean solve(int n) {
- tmpY = new double[n - 3];
- tmpY2 = new double[n - 3];
- int asd = 150;
- for (int i1 = 0; i1 < n && asd > 0; i1++) {
- for (int i2 = i1 + 1; i2 < n && asd > 0; i2++) {
- for (int i3 = i2 + 1; i3 < n && asd > 0; i3++) {
- if (iste(i1, i2) && iste(i2, i3) && iste(i3, i1)) {
- continue;
- }
- asd--;
- for (int j1 = 0; j1 < n; j1++) {
- if (j1 > 0 && isteY(j1, j1 - 1)) continue;
- Point p1 = new Point(x[i1], y[j1]);
- for (int j2 = 0; j2 < n; j2++) {
- if (j2 == j1) continue;
- if (j2 > 0 && isteY(j2, j2 - 1)) continue;
- Point p2 = new Point(x[i2], y[j2]);
- for (int j3 = 0; j3 < n; j3++) {
- if (j3 == j1 || j3 == j2) continue;
- if (j3 > 0 && isteY(j3, j3 - 1)) continue;
- Point p3 = new Point(x[i3], y[j3]);
- // Nadji centar
- Circle c = null;
- try {
- c = new Circle(p1, p2, p3);
- // System.out.println(p1);
- // System.out.println(p2);
- // System.out.println(p3);
- } catch (NullPointerException e) {
- asd++;
- continue;
- } catch (IllegalArgumentException e) {
- asd++;
- continue;
- }
- int k = 0;
- for (int i = 0; i < n; i++) {
- if (i == j1 || i == j2 || i == j3) continue;
- if (y[i] > c.getCenter().getY()) {
- tmpY[k++] = 2 * c.getCenter().getY() - y[i];
- } else {
- tmpY[k++] = y[i];
- }
- }
- boolean ccc = false;
- k = 0;
- for (int i = 0; i < n; i++) {
- if (i == i1 || i == i2 || i == i3) {
- continue;
- }
- double d = (c.getRadius() * c.getRadius() -
- Math.pow(x[i] - c.getCenter().getX(), 2.0));
- if (d < 0) {
- ccc = true;
- break;
- }
- double AA =
- Math.sqrt(d);
- tmpY2[k++] = c.getCenter().getY() - AA;
- }
- if (ccc) continue;
- Arrays.sort(tmpY);
- Arrays.sort(tmpY2);
- boolean all = true;
- for (int i = 0; i < k; i++) {
- if (Math.abs(tmpY[i] - tmpY2[i]) > 1e-10) {
- all = false;
- }
- }
- if (all) {
- return true;
- }
- }
- }
- }
- }
- }
- }
- return false;
- }
- private boolean isteY(int i, int j) {
- return Math.abs(y[i] - y[j]) < 1e-10;
- }
- private boolean iste(int i, int j) {
- return Math.abs(x[i] - x[j]) < 1e-10;
- }
- public static void main(String[] args) {
- new C().solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement