C9.cc

gistfile1.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long double flt;
const flt eps = 1e-10;
const int MAXN = 100;

int sgn(flt x) {
  if (x < -eps) return -1;
  else return x > eps;
}

struct Point {
  flt x, y;
  Point() {}
  Point(flt x, flt y): x(x), y(y) {}
  bool operator == (const Point &rhs) const {
    return sgn(x - rhs.x) == 0 && sgn(y - rhs.y) == 0;
  }
  Point operator + (const Point &rhs) const {
    return Point(x + rhs.x, y + rhs.y);
  }
  Point operator - (const Point &rhs) const {
    return Point(x - rhs.x, y - rhs.y);
  }
  flt det(const Point &rhs) const {
    return x * rhs.y - y * rhs.x;
  }
  flt sqr() const {
    return x * x + y * y;
  }
  flt len() const {
    return hypot(x, y);
  }
}P[MAXN];

flt x[MAXN], y[MAXN];
int n, id[MAXN];

bool getC(Point p1, Point p2, Point p3, Point &C) {
  flt t1,t2,t3;
  if (p1 == p2 || p1 == p3 || p2 == p3) return false;
  if (sgn((p1 - p2).det(p3 - p2)) == 0) return false;
  t1=p1.x*p1.x+p1.y*p1.y-p2.x*p2.x-p2.y*p2.y;
  t2=p1.x*p1.x+p1.y*p1.y-p3.x*p3.x-p3.y*p3.y;
  t3=2*(p1.x-p2.x)*(p1.y-p3.y)-2*(p1.x-p3.x)*(p1.y-p2.y);
  C.x=((p1.y-p3.y)*t1-(p1.y-p2.y)*t2)/t3;
  C.y=-((p1.x-p3.x)*t1-(p1.x-p2.x)*t2)/t3;
  return true;
}

vector<int> G[MAXN];
int mt[MAXN], vis[MAXN];

bool aug(int u) {
  for (auto &v : G[u]) if (!vis[v]) {
    vis[v] = true;
    if (mt[v] == -1 || aug(mt[v])) {
      mt[v] = u; return true;
    }
  }
  return false;
}

bool check(int a, int b, int c) {
  Point O;
  Point A(x[0], y[a]), B(x[1], y[b]), C(x[2], y[c]);
  if (!getC(A, B, C, O)) return false;
  flt r = (A - O).sqr();
  //cout << r << endl;
  for (int i = 0; i < n; ++ i) G[i].clear();
  for (int i = 3; i < n; ++ i) {
    for (int j = 0; j < n; ++ j) {
      if (j == a || j == b || j == c) continue;
      Point T(x[i], y[j]);
      if (sgn((O - T).sqr() - r) == 0) {
        //cout << i << "->" << j << endl;
        G[i].push_back(j);
      }
    }
  }
  memset(mt, -1, sizeof(mt));
  int ret = 0;
  for (int i = 3; i < n; ++ i) {
    memset(vis, 0, sizeof(vis));
    if (aug(i)) ++ ret;
  }
  return ret == n - 3;
}

int main() {
  srand(time(NULL));
  int T; cin >> T;
  while (T --) {
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> x[i];
    for (int i = 0; i < n; ++ i) cin >> y[i];
    bool flag = false;
    for (int _ = 0; _ < 10; ++ _) {
      for (int i = 0; i < n && !flag; ++ i) {
        for (int j = 0; j < n && !flag; ++ j) {
          for (int k = 0; k < n && !flag; ++ k) {
            if (i != j && i != k && j != k && check(i, j, k)) {
              flag = true;
              break;
            }
          }
        }
      }
      random_shuffle(x, x + n);
    }
    if (flag) puts("YES");
    else puts("NO");
  }
  return 0;
}