Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<iostream>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- const int N = 1000;
- double eps = 1e-8;
- double x[N];
- double y[N];
- double x_dbl[N];
- double y_dbl[N];
- bool y_marked[N];
- int n;
- void build_line(double x1, double y1, double x2, double y2, double& A, double& B, double& C)
- {
- A = y1 - y2;
- B = x2 - x1;
- C = x1*y2 - x2*y1;
- }
- void build_circ(double x1, double x2, double x3, double y1, double y2, double y3, double& x0, double& y0, double& r)
- {
- double A1, B1, C1;
- build_line(x1, y1, x2, y2, A1, B1, C1);
- double A2, B2, C2;
- build_line(x1, y1, x3, y3, A2, B2, C2);
- double A3, B3, C3;
- double A4, B4, C4;
- if (A1 == 0)
- {
- A1 = 1;
- B1 = 0;
- }
- if (B1 == 0)
- {
- A1 = 0;
- B1 = 1;
- }
- if (B2 == 0)
- {
- B2 = 1;
- A2 = 0;
- }
- if (A2 == 0)
- {
- A2 = 1;
- B2 = 0;
- }
- build_line((x1 + x2)/2, (y1 + y2)/2, (x1 + x2)/2 + A1, (y1 + y2)/2 + B1, A3, B3, C3);
- build_line((x1 + x3)/2, (y1 + y3)/2, (x1 + x3)/2 + A2, (y1 + y3)/2 + B2, A4, B4, C4);
- if (abs(A3*B4 - A4*B3) < eps)
- {
- x0 = 0; y0 = 0; r = -1;
- }
- else
- {
- x0 = (B3*C4 - B4*C3)/(A3*B4 - A4*B3);
- y0 = (C3*A4 - C4*A3)/(A3*B4 - A4*B3);
- r = (x1 - x0)*(x1 - x0) + (y1 - y0)*(y1 - y0);
- }
- }
- bool go(double x1, double x2, double x3, double y1, double y2, double y3, double* x, double* y)
- {
- double r, y0, x0;
- build_circ(x1, x2, x3, y1, y2, y3, x0, y0, r);
- if (r == -1)
- return false;
- for (int i = 0; i < n; i++)
- {
- if ((x[i] - x0)*(x[i] - x0) > r)
- {
- return false;
- }
- double yy = r - (x[i] - x0)*(x[i] - x0);
- bool can = 0;
- for (int j = 0; (j < n) && (!can); j++)
- {
- can = 0;
- if (abs((y[j] - y0)*(y[j] - y0) - yy) < eps && y_marked[j] == 0)
- {
- can = 1;
- y_marked[j] = 1;
- }
- }
- if (!can)
- return false;
- }
- return true;
- }
- int main()
- {
- freopen("5.in" ,"r", stdin);
- freopen("5_2.out", "w", stdout);
- int t;
- cin >> t;
- for (int i = 0; i < t; i++)
- {
- cin >> n;
- for (int j = 0; j < n; j++)
- {
- cin >> x[j];
- x_dbl[j] = x[j];
- }
- for (int j = 0; j < n; j++)
- {
- cin >> y[j];
- y_dbl[j] = y[j];
- }
- sort(x, x + n);
- sort(y, y + n);
- int mx = unique(x_dbl, x_dbl + n) - x_dbl;
- int my = unique(y_dbl, y_dbl + n) - y_dbl;
- if (mx >= 3)
- {
- bool ans = false;
- for (int i1 = 0; i1 < n; i1++)
- for (int i2 = 0; i2 < n; i2++)
- {
- if (i1 == i2) continue;
- for (int i3 = 0; i3 < n; i3++)
- {
- if (i3 == i1 || i3 == i2) continue;
- for (int j = 0; j < n; j++)
- y_marked[j] = 0;
- ans |= go(x_dbl[0], x_dbl[1], x_dbl[2], y[i1], y[i2], y[i3], x, y);
- }
- }
- if (ans)
- {
- cout << "YES" << endl;
- continue;
- }
- }
- else if (my >= 3)
- {
- bool ans = false;
- for (int i1 = 0; i1 < n; i1++)
- {
- for (int i2 = 0; i2 < n; i2++)
- {
- if (i1 == i2) continue;
- for (int i3 = 0; i3 < n; i3++)
- {
- for (int j = 0; j < n; j++)
- y_marked[j] = 0;
- if (i3 == i1 || i3 == i2) continue;
- ans |= go(y_dbl[0], y_dbl[1], y_dbl[2], x[i1], x[i2], x[i3], y, x);
- }
- }
- }
- if (ans)
- {
- cout << "YES" << endl;
- continue;
- }
- }
- else
- {
- cout << "abacaba" << endl;
- continue;
- }
- cout << "NO" << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement