API tools faq
paste
Advertisement
jeff69

يلعن ايري

jeff69
Feb 1st, 2016
122
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.12 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. #define P(x,y) make_pair(x,y)
  3. using namespace std;
  4. typedef vector<int> vi ;
  5. typedef vector<string> vs ;
  6. typedef vector<double> vd ;
  7. #define sz(x) ((int)(x).size())
  8. #define all(x) x.begin(),x.end()
  9. #define pb(x) push_back(x)
  10. #define EPS 1e-11
  11. #define dot(a,b) ((conj(a)*(b)).real())
  12. #define cross(a,b) ((conj(a)*(b)).imag())
  13. typedef complex< long double > point;
  14. #define X real()
  15. #define Y imag()
  16. #define length(a) hypot((a).real(),(a).imag())
  17. #define length2(a) dot(a,a)
  18. #define normalize(a) ((a)/length(a))
  19. #define polar(r,theta) r*exp(point(0,theta))
  20. #define vect(p1,p2) ((p2)-(p1))
  21. #define mid(p1,p2) ((p1)+(p2))/point(2,0)
  22. #define same(a,b) (length2(vect(a,b))<EPS)
  23. #define angle(a) atan2((a).imag(),(a).real())
  24. const long double pi = acos(-1);
  25.  
  26.  
  27. int compare(long double d1,long double d2)
  28. {
  29. if(fabs(d1-d2) < EPS) return 0;
  30. if(d1<d2) return -1;
  31. return 1;
  32. }
  33.  
  34. bool lineIntersect(point a,point b, point p, point q, point& r)
  35. {
  36. long double d1 = cross(p-a,b-a);
  37. long double d2 = cross(q-a,b-a);
  38.  
  39. if(fabs(d2-d1)<EPS)
  40. return false;
  41. r = (d1*q - d2*p)/ (d1-d2);
  42. return true;
  43. }
  44. bool isPointOnLine(point a,point b, point p) // btgeb eza kan el p 3la el line elle 3lehel 2 points a,b
  45. {
  46. return fabs(cross(vect(a,b),vect(a,p)))<EPS;
  47. }
  48.  
  49. bool isPointOnRay(point a,point b, point p) // btgeb eza kan el
  50. {
  51. return dot(vect(a,b),vect(a,p))>-EPS && isPointOnLine(a,b,p);
  52.  
  53. }
  54. bool isPointOnSegment(point a,point b, point p) // btgeb eza kan el
  55. {
  56. return dot(vect(a,b),vect(a,p))>-EPS && isPointOnLine(a,b,p) && dot(vect(b,a),vect(b,p))>-EPS;
  57. }
  58.  
  59. /*long long double cosineRule(long long double a,long long double b,long long double c) // btgeb el zwya ben el b,c
  60. {
  61. long long double x =( b*b + c*c - a*a) / (2*b*c);
  62. // btgeb el angle elle 2osad el a
  63. if(x>1)x =1;
  64. if(x<-1)x=-1;
  65. return acos(x);
  66. }*/
  67.  
  68. // if we have 2 angels A & B and a side length b this function returns the side length a
  69. long double sinRuleGetSide(long double A,long double B,long double b)
  70. {
  71. return (sin(A)*b)/sin(B);
  72. }
  73.  
  74. // if we have 2 sides lengths a & b and an angel B this function returns the angel A
  75. long double sinRuleGetAngel(long double a,long double b,long double B)
  76. {
  77. long double A=(a*sin(B))/b;
  78. if(A>1)a=1;
  79. if(A<-1)a=-1;
  80. return asin(A);
  81. }
  82.  
  83. // checking intersection
  84. int isIntersecting(point c1,point c2,long double r1,long double r2)
  85. {
  86. // 0 if no intersection
  87. // 1 if normally intersecting
  88. // 2 if outside tangent
  89. // 3 if inside tangent
  90. // 4 if C1 contain C2
  91. // 5 if same circule
  92.  
  93. if(compare(r1+r2, length(c1-c2))<0) return 0; // no intersection
  94. if(compare(length(c1-c2),fabs(r1-r2))<0) return 4; // no intersection
  95. if(length(c1-c2)<EPS && compare(r1,r2) == 0) return 5; // same circule
  96.  
  97. if(compare(r1+r2 ,length(c1-c2)) == 0) return 2;
  98. if(compare(fabs(r1-r2),length(c1-c2))== 0) return 3;
  99. if(compare(r1+r2,length(c1-c2)) > 0) return 1;
  100.  
  101. }
  102.  
  103. /*void circuleIntersection(point c1,point c2,long double r1,long double r2,point& p1,point& p2)
  104. {
  105. if(r1<r2)
  106. {
  107. swap(r1,r2);
  108. swap(c1,c2);
  109. }
  110. long double theta1 = angle(c2-c1); long long double theta2 = cosineRule(r2,r1,length(c2-c1));
  111. p1 = polar(r1, theta1+theta2)+c1;
  112. p2 = polar(r1, theta1-theta2)+c1;
  113. }*/
  114.  
  115. bool lineCirculeIntersection(point p0,point p1,point C,long double r,point& r1,point& r2)
  116. {
  117. // p0,p1 -> line
  118. // C,r ->circle
  119. long double a = dot(p1-p0,p1-p0);
  120. long double b = 2*dot(p1-p0,p0-C);
  121. long double c = dot(p0-C,p0-C)- r*r;
  122.  
  123. long double x = b*b-(4*a*c);
  124. if(x<-1*EPS) return false; // law el rkam b negative 3shan ma3mlsh square root l x:D
  125. if(fabs(x)<EPS) x = 0;
  126. long double t1 = (-1*b + sqrt(x))/(2*a);
  127. long double t2 = (-1*b - sqrt(x))/(2*a);
  128. r1 = p0 + t1*(p1-p0);
  129. r2 = p0 + t2*(p1-p0);
  130. return true;
  131. }
  132.  
  133.  
  134. /*
  135. For convex HULL
  136. */
  137.  
  138. struct cmp{
  139. point about;
  140. cmp(point c)
  141. {
  142. about = c;
  143. }
  144. bool operator()(const point& p,const point& q)const
  145. {
  146. long double cr = cross(vect(about,p),vect(about,q));
  147. if(fabs(cr)<EPS)
  148. return make_pair(p.Y,p.X)< make_pair(q.Y,q.X);
  149. return cr>0;
  150. }
  151. };
  152.  
  153. vector<point> pnts;
  154. vector<point> convex;
  155.  
  156. void convexHull()
  157. {
  158. point mn(1/0.0,1/0.0);
  159. for(int i = 0 ; i < sz(pnts) ; i++)
  160. {
  161. if(make_pair(pnts[i].Y,pnts[i].X) < make_pair(mn.Y,mn.X))
  162. mn= pnts[i];
  163. }
  164. sort(all(pnts),cmp(mn));
  165. convex.clear();
  166. convex.push_back(pnts[0]);
  167. if(sz(pnts)==1)return ;
  168. convex.push_back(pnts[1]);
  169. for(int i = 2; i <= sz(pnts) ; i++)
  170. {
  171. point c = pnts[i%sz(pnts)];
  172. while(sz(convex)>1)
  173. {
  174. point b = convex.back();
  175. point a = convex[sz(convex)-2];
  176. if(cross(vect(b,a),vect(b,c))<-EPS)
  177. break;
  178. convex.pop_back();
  179. }
  180. if(i<sz(pnts))
  181. convex.push_back(pnts[i]);
  182.  
  183. }
  184. }
  185.  
  186. //to rotate point
  187. point rotate_by(const point &p, const point &about, long double radians)
  188. {
  189. return (p - about) * exp(point(0, radians)) + about;
  190. }
  191.  
  192. //to reflect point
  193. point reflect(const point &p, const point &about1, const point &about2)
  194. {
  195. point z = p - about1;
  196. point w = about2 - about1;
  197. return conj(z / w) * w + about1;
  198. }
  199.  
  200.  
  201. bool testColinearPoints(const point& a,const point& b,const point& c)
  202. {
  203. return fabs(cross(b-a,c-b)) < EPS;
  204. }
  205.  
  206. long double pointLineDistance(const point& a,const point& b,const point& p) // ab is the line and other is the point
  207. {
  208. return fabs(cross(b-a,p-a))/length(b-a);
  209. }
  210.  
  211. long double pointSegmentDistance(const point& a,const point& b,const point& p)
  212. {
  213. if(dot(p-a,b-a)<=0)return length(p-a);
  214. if(dot(p-b,a-b)<=0)return length(p-b);
  215. return pointLineDistance(a,b,p);
  216. }
  217.  
  218.  
  219. enum states{EXTERIOR,INTERIOR,BOUNDARY};
  220.  
  221. int inSidePolygon(vector<point> polygon,point p)
  222. {
  223. int counter = 0;
  224. int i;
  225. long double xinters;
  226. point p1,p2;
  227. int N = polygon.size();
  228. p1 = polygon[0];
  229. for (i=1;i<=N;i++) {
  230. p2 = polygon[i % N];
  231. if (p.Y > min(p1.Y,p2.Y)) {
  232. if (p.Y <= max(p1.Y,p2.Y)) {
  233. if (p.X <= max(p1.X,p2.X)) {
  234. if (p1.Y != p2.Y) {
  235. xinters = (p.Y-p1.Y)*(p2.X-p1.X)/(p2.Y-p1.Y)+p1.X;
  236. if (p1.X == p2.X || p.X <= xinters)
  237. counter++;
  238. }
  239. }
  240. }
  241. }
  242. if(pointSegmentDistance(p1,p2,p) == 0) return 2; //point on segment
  243. p1 = p2;
  244.  
  245. }
  246.  
  247. if (counter % 2)
  248. return 1;
  249. else
  250. return 0;
  251. }
  252.  
  253.  
  254. long double polygonArea(vector<point> pol)
  255. {
  256. long double res=0;
  257. pol.push_back(pol[0]);
  258.  
  259. for(int i = 0 ; i < (int)pol.size()-1 ; i ++)
  260. {
  261. res+=cross(pol[i],pol[i+1]);
  262. }
  263. res/=2;
  264. return res;
  265. }// if points are given in anti clockwise -> res will be positive else negative
  266.  
  267. long double traingleArea(long double a,long double b, long double c)// heron's formula
  268. {
  269. long double s = (a+b+c)/2;
  270. return sqrt(s*(s-a)*(s-b)*(s-c));
  271. }
  272.  
  273. pair<point,double> getCircle2(point a, point b) // el long double el awalane el center we el tane el raduis
  274. {
  275. // a, b are diameter(kotr)
  276. return make_pair((a+b)/point(2,0),length(b-a)/2);
  277. }
  278.  
  279. pair<point,double> getCircle3(point a, point b, point c) // el long double el awalane el center we el tane el raduis
  280. {
  281.  
  282. point v1 = vect(a,b);
  283. point mid1 =(b+a)/point(2,0);
  284. point p1 (-1*v1.Y,v1.X);
  285. p1+=mid1;
  286. point v2 = vect(b,c);
  287. point mid2 = (c+b)/point(2,0);
  288. point p2(-1*v2.Y,v2.X);
  289. p2+= mid2;
  290. point C;
  291. lineIntersect(mid1,p1,mid2,p2,C);
  292. return make_pair(C,length(C-a));
  293. }
  294.  
  295.  
  296. // minimum enclosing circle
  297. // random_shuffle(pnts.begin(),pnts.end()); lazem shuffle 2bl el ms2la 3shan at2kd en hya htege fe n
  298. #define MAXSIZE 100
  299. int ps = 0,rs = 0;
  300. point pts[MAXSIZE],rem[3];
  301. pair<point,double> cir;
  302. void mec()
  303. {
  304. if(rs==3)
  305. {
  306. cir= getCircle3(rem[0],rem[1],rem[2]);
  307. return;
  308. }
  309. if(ps == 0)
  310. {
  311. if(rs==2)
  312. cir = getCircle2(rem[0],rem[1]);
  313. else
  314. cir = make_pair(rem[0],0);
  315. return ;
  316. }
  317. ps--;
  318. mec();
  319. if(length2(vect(pts[ps],cir.first))>cir.second*cir.second){
  320. rem[rs++]=pts[ps];
  321. mec();
  322. rs--;
  323. }
  324. ps++;
  325. }
  326.  
  327.  
  328. long double circumference(long double r)
  329. {
  330. return 2*pi*r;
  331. }
  332.  
  333. void polygonCut(vector<point>& input, vector<point>& res,const point& a,const point& b)//input is anti clockwise
  334. {
  335. // take care of removing duplicate points
  336. res.clear();
  337. point p,q;
  338. for(int i= 0 ; i < sz(input) ; i ++)
  339. {
  340. p = input[i];
  341. q = input[(i+1)%sz(input)];
  342. bool b1,b2;
  343. b1 = cross(vect(a,b),vect(a,p))> -EPS;
  344. b2 = cross(vect(a,b),vect(a,q))> -EPS;
  345. if(b1)
  346. res.push_back(p);
  347. if(b1^b2)
  348. {
  349. point r;
  350. lineIntersect(b,a,p,q,r);
  351. res.push_back(r);
  352. }
  353. }
  354. }
  355.  
  356. void convexPolygonIntersection(vector<point> p1,vector<point> p2,vector<point>& res)
  357. {
  358. vector<point> temp ;
  359. res= p1;
  360. point p,q;
  361. for(int i = 0 ; i < sz(p2) ; i++)
  362. {
  363. p = p2[i];
  364. q = p2[(i+1)%sz(p2)];
  365. polygonCut(res,temp,p,q);
  366. res = temp;
  367. }
  368. }
  369.  
  370. void voronoi(vector<point> inp, long double xmn,long double ymn,long double xmx,long double ymx,vector<vector<point> >& res)
  371. {
  372. res.clear();
  373. point p,q;
  374. vector<point> tmp2;
  375. for(int i = 0 ; i < sz(inp) ; i ++)
  376. {
  377. vector<point> tmp;
  378. tmp.push_back(point(xmn,ymn));
  379. tmp.push_back(point(xmx,ymn));
  380. tmp.push_back(point(xmx,ymx));
  381. tmp.push_back(point(xmn,ymx));
  382. p = inp[i];
  383. for(int j = 0 ; j < sz(inp) ; j++)
  384. {
  385. if(i==j)continue;
  386. q = inp[j];
  387. point k = mid(p,q);
  388. point pq = vect(p,q);
  389. point prb = point(-pq.Y,pq.X);
  390. polygonCut(tmp,tmp2,k,k+prb);
  391. tmp = tmp2;
  392. }
  393. res.push_back(tmp);
  394. }
  395.  
  396. }
  397. // TAKE CARE this function fails if polygon intersects with itself
  398.  
  399. // return the centroid point of the polygon
  400. // The centroid is also known as the "centre of gravity" or the "center of mass". The position of the centroid
  401. // assuming the polygon to be made of a material of uniform density.
  402. point polygin_centroid(vector<point> &polygon)
  403. {
  404. pair < long double , long double > res;
  405. long double a = 0;
  406. //res.X += 9.0;
  407. for( int i= 0 ; i < sz(polygon) ; i++ )
  408. {
  409. int j = (i+1) % sz(polygon);
  410.  
  411. res.first += (polygon[i].X + polygon[j].X)* (polygon[i].X * polygon[j].Y - polygon[j].X * polygon[i].Y);
  412. res.second += (polygon[i].Y+polygon[j].Y)* (polygon[i].X * polygon[j].Y - polygon[j].X * polygon[i].Y);
  413. a += polygon[i].X * polygon[j].Y - polygon[i].Y * polygon[j].X;
  414. }
  415.  
  416. a *= 0.5;
  417. res.first /= (6.0 * a);
  418. res.second /= (6.0 * a);
  419.  
  420. return point(res.first , res.second);
  421. }
  422. const int MX=(1<<20);
  423. point p[MX];
  424. int n;
  425. vector < int > v;
  426. int main(){
  427. #ifndef ONLINE_JUDGE
  428. freopen("in.in","r",stdin);
  429. #endif // ONLINE_JUDGE
  430. cin>>n;
  431. for(int j=1;j<=n;j++){
  432. int a , b;
  433. scanf("%d %d",&a,&b);
  434. p[j] = point(a,b);
  435. }
  436. int a = 1 , b = 2;
  437. for(int j=3;j<=n;j++){
  438. if(testColinearPoints(p[a] , p[b] , p[j])){
  439. if(compare(length(vect(p[a] , p[b])) , length(vect(p[a] , p[j]))) == 1)
  440. b=j;
  441. }
  442. }
  443. long double mn = 1e50;
  444. int c=100;
  445. for(int j=1;j<=n;j++){
  446. if(j==a || j==b) continue;
  447. if(testColinearPoints(p[a] , p[b] , p[j])) {
  448. // puts("sex");
  449. continue;
  450. }
  451. vector < point > P;
  452. P.push_back(p[a]);
  453. P.push_back(p[b]);
  454. P.push_back(p[j]);
  455. long double area = traingleArea(length(vect(p[a] , p[b])) , length(vect(p[a] , p[j])) , length(vect(p[j] , p[b]))); // cout<<j<<' '<<area<<endl;
  456. if(compare(mn , area) == 1){
  457. mn=area;
  458. c=j;
  459. }
  460. }
  461. cout<<a<<' '<<b<<' '<<c<<endl;
  462.  
  463. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!