Advertisement
Guest User

Untitled

a guest
Feb 28th, 2015
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.09 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:66777216")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. //#include <bits/stdc++.h>
  4. //#include <unordered_set>
  5. //#include <unordered_map>
  6. #include <functional>
  7. #include <algorithm>
  8. #include <iostream>
  9. #include <sstream>
  10. #include <fstream>
  11. #include <cassert>
  12. #include <iomanip>
  13. #include <complex>
  14. #include <cstring>
  15. #include <cstdio>
  16. #include <bitset>
  17. #include <string>
  18. #include <vector>
  19. #include <ctime>
  20. #include <queue>
  21. #include <stack>
  22. #include <cmath>
  23. #include <list>
  24. #include <set>
  25. #include <map>
  26. //#include <decimal>
  27. //#include <boost/multiprecision/mpfr.hpp>
  28.  
  29. #define forn(i,n) for(int i = 0; i < (int)(n); ++ i)
  30. #define for1(i,n) for(int i = 1; i <= (int)(n); ++ i)
  31. #define fore(i,a,b) for(int i = (int)(a); i <= (int)(b); ++ i)
  32. #define ford(i,n) for(int i = (int)(n)-1; i >= 0; -- i)
  33. #define ford1(i,n) for(int i = (int)(n); i >= 1; -- i)
  34. #define fored(i,a,b) for(int i = (int)(b); i >= (int)(a);--i)
  35. #define mp make_pair
  36. #define pb push_back
  37. #define sz(v) ((int)((v).size()))
  38. #define all(v) (v).begin(), (v).end()
  39. #define FOR(i, n) for (int i = 0; i < (n); ++i)
  40. //#define FORE(it,c) for(__typeof(c).begin() it = (c).begin(); it!=(c).end(); ++it)
  41. //#define fi first
  42. //#define se second
  43.  
  44. using namespace std;
  45.  
  46. typedef unsigned long long ULL;
  47. typedef long long LL;
  48. typedef long double LD;
  49. //typedef unsigned int UI;
  50.  
  51. typedef long long i64;
  52. typedef unsigned long long u64;
  53. typedef long double ld;
  54. typedef vector<bool> vb;
  55. typedef vector<int> vi;
  56. typedef vector<vi> vvi;
  57. typedef pair<int,int> pii;
  58. typedef pair<LL,LL> pll;
  59. typedef vector<pii> vpi;
  60. typedef vector<ld> vd;
  61. typedef pair<ld,ld> pdd;
  62. typedef vector<pdd> vpd;
  63.  
  64. const LD ep = 1e-8;
  65.  
  66.  
  67. bool EQ(LD a, LD b){
  68. return a < b+ep && b < a+ep;
  69. }
  70.  
  71. int m;
  72. bool collinear(pdd & a, pdd & b, pdd & c){
  73. return EQ((b.first-a.first)*(c.second-a.second),(c.first-a.first)*(b.second-a.second));
  74. }
  75. /*LD D(pdd a, pdd b){
  76. return sqrtl( (b.second-a.second)*(b.second-a.second)+(b.first-a.first)*(b.first-a.first));
  77. }*/
  78. struct coord{
  79. LD x, y;
  80. coord(pdd a){
  81. x = a.first;
  82. y = a.second;
  83. }
  84. coord(LD _x, LD _y){
  85. x = _x;
  86. y = _y;
  87. }
  88. };
  89. struct line{
  90. LD a, b, c;
  91. line(coord o,coord p){
  92. a = o.y-p.y;
  93. b = p.x-o.x;
  94. c = -(a*o.x+b*o.y);
  95. }
  96. };
  97. LD D(coord a, coord b){
  98. return sqrtl( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  99. }
  100. coord AD(coord a, coord b){
  101. return coord(a.x+b.x,a.y+b.y);
  102. }
  103. coord intersect(line d,line e){
  104. 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) );
  105. }
  106. line ukh(coord a, coord b){
  107. LD d1 = D(a,b);
  108. coord v1(b.x-a.x, b.y-a.y);
  109. v1.x/=2.0;
  110. v1.y/=2.0;
  111. coord m = AD(a,v1);
  112. coord m2 = AD(m, coord(-v1.y,v1.x) );
  113. return line(m,m2);
  114. }
  115. coord center(pdd P1,pdd P2,pdd P3){
  116. coord p1(P1), p2(P2), p3(P3);
  117. line l1 = ukh(p1,p2);
  118. line l2 = ukh(p1,p3);
  119. coord o = intersect(l1,l2);
  120. //cerr<<l1.a*o.x+l1.b*o.y+l1.c<<endl;
  121. /* while(!EQ(l1.a*o.x+l1.b*o.y+l1.c,0)){
  122. EQ(l1.a*o.x+l1.b*o.y+l1.c,0);
  123. break;
  124. }
  125. while(!EQ(l2.a*o.x+l2.b*o.y+l2.c,0)){
  126. EQ(l2.a*o.x+l2.b*o.y+l2.c,0);
  127. break;
  128. }
  129. assert(EQ(l1.a*o.x+l1.b*o.y+l1.c,0));
  130. assert(EQ(l2.a*o.x+l2.b*o.y+l2.c,0));*/
  131. return o;
  132. /* LD d1 = D(P1,P2);
  133. LD d2 = D(P1,P3);
  134. coord v1(mp(P2.first-P1.first,P2.second-P1.second));
  135. coord v2(mp(P3.first-P1.first,P3.second-P1.second));
  136. v1.x/=2.0;
  137. v1.y/=2.0;
  138.  
  139. v2.x/=2.0;
  140. v2.y/=2.0;
  141.  
  142. coord m1 = AD(p1,v1);
  143. coord m2 = AD(p1,v2);
  144. */
  145. }
  146. int n;
  147. bool check(vd & x, vd & y){
  148. forn(i,n){
  149. if(x[i] < -ep)
  150. x[i] = -x[i];
  151. if(y[i] < -ep)
  152. y[i] = -y[i];
  153. }
  154. sort(all(x));
  155. sort(all(y));
  156. reverse(all(y));
  157. forn(i,n)
  158. if(!EQ(x[i]*x[i]+y[i]*y[i],x[0]*x[0]+y[0]*y[0]))
  159. return false;
  160. return true;
  161. }
  162. void solve(const char * ci, const char * co){
  163. ifstream fin(ci);
  164. ofstream fout(co);
  165.  
  166. /* int T;
  167. fin>>T;
  168.  
  169. while(T--){
  170. int m;
  171. fin>>m;
  172. vvi a(m);
  173. int S = 0;
  174. int ma = 1000, mt = 0;
  175. forn(i,m){
  176. int k;
  177. fin>>k;
  178. a[i].resize( k );
  179. forn(j,k){
  180. fin>>a[i][j];
  181. mt = max(mt,a[i][j]);
  182. }
  183. ma = min(ma,k);
  184. S+=k;
  185. }
  186. cerr<<m<<" "<<ma<<" "<<S<<" "<<mt<<endl;
  187. }*/
  188. int T;
  189. int S = 0;
  190. fin>>T;
  191. LD mi = 0;
  192. while(T--){
  193.  
  194. fin>>n;
  195. S+=n*n*n*n;
  196. vector< LD > x(n), y(n);
  197. forn(i,n)
  198. fin>>x[i];
  199. forn(i,n)
  200. fin>>y[i];
  201. /* if(n <= 2){
  202. fout<<"NO"<<endl;
  203. continue;
  204. }
  205. */
  206. forn(i,n){
  207. mi = max(mi, abs(y[i]));
  208. mi = max(mi, abs(x[i]));
  209. /* if(y[i] - y[i-1] < 1e-17)
  210. continue;
  211. mi = min(y[i]-y[i-1],mi);*/
  212. }
  213. sort(all(x));
  214. sort(all(y));
  215. bool flag = false;
  216. for1(i,n-1){
  217. if(!EQ(x[i],x[0])){
  218. flag = true;
  219. swap(x[1],x[i]);
  220. break;
  221. }
  222. }
  223. if(!flag){
  224. swap(x,y);
  225. bool flag2 = false;
  226. for1(i,n-1){
  227. if(!EQ(x[i],x[0])){
  228. flag2 = true;
  229. swap(x[1],x[i]);
  230. break;
  231. }
  232. }
  233. if(!flag2){
  234. fout<<"NO"<<endl;
  235. continue;
  236. }
  237. }
  238. //x[0]!=x[1]
  239. assert(!EQ(x[0],x[1]));
  240. bool flag2 = false;
  241. for(int i = 2; i < n; ++ i){
  242. if(!EQ(x[i],x[0]) && !EQ(x[i],x[1])){
  243. flag2 = true;
  244. swap(x[2],x[i]);
  245. break;
  246. }
  247. }
  248. vd X(n);
  249. vd Y(n);
  250. if(flag2){
  251. forn(i,n){
  252. forn(j,n){
  253. if(i==j)continue;
  254. forn(k,n){
  255. if(k==i || k==j)continue;
  256. pair<LD,LD> p1 = mp(x[0],y[i]),p2 = mp(x[1],y[j]),p3 = mp(x[2],y[k]);
  257. if(collinear(p1,p2,p3))continue;
  258. coord c = center(p1,p2,p3);
  259. //(x[0],y[i]) (x[1],y[j])
  260. forn(t,n){
  261. X[t] = x[t]-c.x;
  262. Y[t] = y[t]-c.y;
  263. }
  264. if(check(X, Y)){
  265. fout<<"YES"<<endl;
  266. goto x;
  267. }
  268. }
  269. }
  270. }
  271. fout<<"NO"<<endl;
  272. x:
  273. int prosto;
  274. }else{
  275. assert(false);
  276. }
  277.  
  278. /* reverse(all(y));
  279. bool flag = true;;
  280. forn(i,n){
  281. if(!EQ(x[i]*x[i]+y[i]*y[i],x[0]*x[0]+y[0]*y[0]))
  282. flag = false;
  283. }
  284. if(flag || ){
  285. fout<<"YES"<<endl;
  286. }else{
  287. fout<<"NO"<<endl;
  288. }*/
  289. }
  290. cerr<<mi<<endl;
  291. cerr<<ci<<" "<<S<<endl;
  292. /* int T, n;
  293. fin>>T;
  294. while(T--){
  295. fin>>n;
  296. vvi a(n);
  297. forn(i,n){
  298. int k;
  299. fin>>k;
  300. a[i].resize(k);
  301. forn(j,k)
  302. fin>>a[i][j];
  303. }
  304. }*/
  305. }
  306. void testgen(){
  307. FILE * file_ = fopen("input.txt", "w");
  308. /* srand(time(NULL));
  309. int n = 3*3, k = 3;
  310. fprintf(file_, "%d\n", n);*/
  311. fclose(file_);
  312. }
  313. char si[100];
  314. char so[100];
  315. int main() {
  316. #ifdef LOCAL
  317. // testgen();
  318. freopen("input.txt", "r", stdin);
  319. // freopen("output.txt", "w", stdout);
  320. #else
  321. #define task "heap"
  322. // freopen("input.txt", "r", stdin);
  323. // freopen("output.txt", "w", stdout);
  324. // freopen(task".in", "r", stdin);
  325. // freopen(task".out", "w", stdout);
  326. #endif
  327.  
  328. cout<<fixed;
  329. cout.precision(15);
  330. cerr<<fixed;
  331. cerr.precision(12);
  332. /* for1(i,9){
  333. si[0] = i+'0';
  334. si[1] = '.';
  335. si[2] = 'i';
  336. si[3] = 'n';
  337.  
  338. so[0] = 'C';
  339. so[1] = i+'0';
  340. so[2] = '.';
  341. so[3] = 'o';
  342. so[4] = 'u';
  343. so[5] = 't';
  344. const char * ci = si;
  345. const char * co = so;
  346. solve(ci, co);
  347. }
  348.  
  349. const char * ci = "10.in";
  350. const char * co = "C10.out";
  351. solve(ci, co);*/
  352. const char * ci = "5.in";//si;
  353. const char * co = "C5.out";//so;
  354. solve(ci, co);
  355.  
  356. #ifdef LOCAL
  357. cerr<<"Execution time = "<<clock()/1000.0<<"ms\n";
  358. #endif
  359. return 0;
  360. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement