Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:66777216")
- #define _CRT_SECURE_NO_WARNINGS
- //#include <bits/stdc++.h>
- //#include <unordered_set>
- //#include <unordered_map>
- #include <functional>
- #include <algorithm>
- #include <iostream>
- #include <sstream>
- #include <fstream>
- #include <cassert>
- #include <iomanip>
- #include <complex>
- #include <cstring>
- #include <cstdio>
- #include <bitset>
- #include <string>
- #include <vector>
- #include <ctime>
- #include <queue>
- #include <stack>
- #include <cmath>
- #include <list>
- #include <set>
- #include <map>
- //#include <decimal>
- //#include <boost/multiprecision/mpfr.hpp>
- #define forn(i,n) for(int i = 0; i < (int)(n); ++ i)
- #define for1(i,n) for(int i = 1; i <= (int)(n); ++ i)
- #define fore(i,a,b) for(int i = (int)(a); i <= (int)(b); ++ i)
- #define ford(i,n) for(int i = (int)(n)-1; i >= 0; -- i)
- #define ford1(i,n) for(int i = (int)(n); i >= 1; -- i)
- #define fored(i,a,b) for(int i = (int)(b); i >= (int)(a);--i)
- #define mp make_pair
- #define pb push_back
- #define sz(v) ((int)((v).size()))
- #define all(v) (v).begin(), (v).end()
- #define FOR(i, n) for (int i = 0; i < (n); ++i)
- //#define FORE(it,c) for(__typeof(c).begin() it = (c).begin(); it!=(c).end(); ++it)
- //#define fi first
- //#define se second
- using namespace std;
- typedef unsigned long long ULL;
- typedef long long LL;
- typedef long double LD;
- //typedef unsigned int UI;
- typedef long long i64;
- typedef unsigned long long u64;
- typedef long double ld;
- typedef vector<bool> vb;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef pair<int,int> pii;
- typedef pair<LL,LL> pll;
- typedef vector<pii> vpi;
- typedef vector<ld> vd;
- typedef pair<ld,ld> pdd;
- typedef vector<pdd> vpd;
- const LD ep = 1e-8;
- bool EQ(LD a, LD b){
- return a < b+ep && b < a+ep;
- }
- int m;
- bool collinear(pdd & a, pdd & b, pdd & c){
- return EQ((b.first-a.first)*(c.second-a.second),(c.first-a.first)*(b.second-a.second));
- }
- /*LD D(pdd a, pdd b){
- return sqrtl( (b.second-a.second)*(b.second-a.second)+(b.first-a.first)*(b.first-a.first));
- }*/
- struct coord{
- LD x, y;
- coord(pdd a){
- x = a.first;
- y = a.second;
- }
- coord(LD _x, LD _y){
- x = _x;
- y = _y;
- }
- };
- struct line{
- LD a, b, c;
- line(coord o,coord p){
- a = o.y-p.y;
- b = p.x-o.x;
- c = -(a*o.x+b*o.y);
- }
- };
- LD D(coord a, coord b){
- return sqrtl( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
- }
- coord AD(coord a, coord b){
- return coord(a.x+b.x,a.y+b.y);
- }
- coord intersect(line d,line e){
- return coord( -(d.c*e.b-e.c*d.b)/(d.a*e.b-e.a*d.b),-(d.c*e.a-e.c*d.a)/(e.a*d.b-d.a*e.b) );
- }
- line ukh(coord a, coord b){
- LD d1 = D(a,b);
- coord v1(b.x-a.x, b.y-a.y);
- v1.x/=2.0;
- v1.y/=2.0;
- coord m = AD(a,v1);
- coord m2 = AD(m, coord(-v1.y,v1.x) );
- return line(m,m2);
- }
- coord center(pdd P1,pdd P2,pdd P3){
- coord p1(P1), p2(P2), p3(P3);
- line l1 = ukh(p1,p2);
- line l2 = ukh(p1,p3);
- coord o = intersect(l1,l2);
- //cerr<<l1.a*o.x+l1.b*o.y+l1.c<<endl;
- /* while(!EQ(l1.a*o.x+l1.b*o.y+l1.c,0)){
- EQ(l1.a*o.x+l1.b*o.y+l1.c,0);
- break;
- }
- while(!EQ(l2.a*o.x+l2.b*o.y+l2.c,0)){
- EQ(l2.a*o.x+l2.b*o.y+l2.c,0);
- break;
- }
- assert(EQ(l1.a*o.x+l1.b*o.y+l1.c,0));
- assert(EQ(l2.a*o.x+l2.b*o.y+l2.c,0));*/
- return o;
- /* LD d1 = D(P1,P2);
- LD d2 = D(P1,P3);
- coord v1(mp(P2.first-P1.first,P2.second-P1.second));
- coord v2(mp(P3.first-P1.first,P3.second-P1.second));
- v1.x/=2.0;
- v1.y/=2.0;
- v2.x/=2.0;
- v2.y/=2.0;
- coord m1 = AD(p1,v1);
- coord m2 = AD(p1,v2);
- */
- }
- int n;
- bool check(vd & x, vd & y){
- forn(i,n){
- if(x[i] < -ep)
- x[i] = -x[i];
- if(y[i] < -ep)
- y[i] = -y[i];
- }
- sort(all(x));
- sort(all(y));
- reverse(all(y));
- forn(i,n)
- if(!EQ(x[i]*x[i]+y[i]*y[i],x[0]*x[0]+y[0]*y[0]))
- return false;
- return true;
- }
- void solve(const char * ci, const char * co){
- ifstream fin(ci);
- ofstream fout(co);
- /* int T;
- fin>>T;
- while(T--){
- int m;
- fin>>m;
- vvi a(m);
- int S = 0;
- int ma = 1000, mt = 0;
- forn(i,m){
- int k;
- fin>>k;
- a[i].resize( k );
- forn(j,k){
- fin>>a[i][j];
- mt = max(mt,a[i][j]);
- }
- ma = min(ma,k);
- S+=k;
- }
- cerr<<m<<" "<<ma<<" "<<S<<" "<<mt<<endl;
- }*/
- int T;
- int S = 0;
- fin>>T;
- LD mi = 0;
- while(T--){
- fin>>n;
- S+=n*n*n*n;
- vector< LD > x(n), y(n);
- forn(i,n)
- fin>>x[i];
- forn(i,n)
- fin>>y[i];
- /* if(n <= 2){
- fout<<"NO"<<endl;
- continue;
- }
- */
- forn(i,n){
- mi = max(mi, abs(y[i]));
- mi = max(mi, abs(x[i]));
- /* if(y[i] - y[i-1] < 1e-17)
- continue;
- mi = min(y[i]-y[i-1],mi);*/
- }
- sort(all(x));
- sort(all(y));
- bool flag = false;
- for1(i,n-1){
- if(!EQ(x[i],x[0])){
- flag = true;
- swap(x[1],x[i]);
- break;
- }
- }
- if(!flag){
- swap(x,y);
- bool flag2 = false;
- for1(i,n-1){
- if(!EQ(x[i],x[0])){
- flag2 = true;
- swap(x[1],x[i]);
- break;
- }
- }
- if(!flag2){
- fout<<"NO"<<endl;
- continue;
- }
- }
- //x[0]!=x[1]
- assert(!EQ(x[0],x[1]));
- bool flag2 = false;
- for(int i = 2; i < n; ++ i){
- if(!EQ(x[i],x[0]) && !EQ(x[i],x[1])){
- flag2 = true;
- swap(x[2],x[i]);
- break;
- }
- }
- vd X(n);
- vd Y(n);
- if(flag2){
- forn(i,n){
- forn(j,n){
- if(i==j)continue;
- forn(k,n){
- if(k==i || k==j)continue;
- pair<LD,LD> p1 = mp(x[0],y[i]),p2 = mp(x[1],y[j]),p3 = mp(x[2],y[k]);
- if(collinear(p1,p2,p3))continue;
- coord c = center(p1,p2,p3);
- //(x[0],y[i]) (x[1],y[j])
- forn(t,n){
- X[t] = x[t]-c.x;
- Y[t] = y[t]-c.y;
- }
- if(check(X, Y)){
- fout<<"YES"<<endl;
- goto x;
- }
- }
- }
- }
- fout<<"NO"<<endl;
- x:
- int prosto;
- }else{
- assert(false);
- }
- /* reverse(all(y));
- bool flag = true;;
- forn(i,n){
- if(!EQ(x[i]*x[i]+y[i]*y[i],x[0]*x[0]+y[0]*y[0]))
- flag = false;
- }
- if(flag || ){
- fout<<"YES"<<endl;
- }else{
- fout<<"NO"<<endl;
- }*/
- }
- cerr<<mi<<endl;
- cerr<<ci<<" "<<S<<endl;
- /* int T, n;
- fin>>T;
- while(T--){
- fin>>n;
- vvi a(n);
- forn(i,n){
- int k;
- fin>>k;
- a[i].resize(k);
- forn(j,k)
- fin>>a[i][j];
- }
- }*/
- }
- void testgen(){
- FILE * file_ = fopen("input.txt", "w");
- /* srand(time(NULL));
- int n = 3*3, k = 3;
- fprintf(file_, "%d\n", n);*/
- fclose(file_);
- }
- char si[100];
- char so[100];
- int main() {
- #ifdef LOCAL
- // testgen();
- freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- #else
- #define task "heap"
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- // freopen(task".in", "r", stdin);
- // freopen(task".out", "w", stdout);
- #endif
- cout<<fixed;
- cout.precision(15);
- cerr<<fixed;
- cerr.precision(12);
- /* for1(i,9){
- si[0] = i+'0';
- si[1] = '.';
- si[2] = 'i';
- si[3] = 'n';
- so[0] = 'C';
- so[1] = i+'0';
- so[2] = '.';
- so[3] = 'o';
- so[4] = 'u';
- so[5] = 't';
- const char * ci = si;
- const char * co = so;
- solve(ci, co);
- }
- const char * ci = "10.in";
- const char * co = "C10.out";
- solve(ci, co);*/
- const char * ci = "5.in";//si;
- const char * co = "C5.out";//so;
- solve(ci, co);
- #ifdef LOCAL
- cerr<<"Execution time = "<<clock()/1000.0<<"ms\n";
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement