Advertisement
Guest User

Ciel and Map

a guest
Aug 23rd, 2014
243
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.41 KB | None | 0 0
  1. //Bismillahir Rahmanir Rahim
  2. /******Harun Or Rashid******/
  3. /***********Template Starts Here***********/
  4. #include<iostream>
  5. #include<cstdio>
  6. #include<cstring>
  7. #include<cmath>
  8. #include<cctype>
  9. #include<cstdlib>
  10. #include<string>
  11. #include<vector>
  12. #include<set>
  13. #include<stack>
  14. #include<queue>
  15. #include<map>
  16. #include<algorithm>
  17. using namespace std;
  18.  
  19. #define MEM(a,b) memset(a,b,sizeof(a))
  20. #define CLR(a) memset(a,0,sizeof(a))
  21. #define MAX(a,b) ((a)>(b)?(a):(b))
  22. #define MIN(a,b) ((a)>(b)?(b):(a))
  23. #define ABS(a) ((a)>0? (a):(-(a)))
  24. #define SQ(a) ((a)*(a))
  25. #define SZ(a) (int)a.size()
  26. #define FORN(i,n) for(i=1;i<=n;i++)
  27. #define FORAB(i,a,b) for(i=a;i<=b;i++)
  28. #define ALL(V) V.begin(),V.end()
  29. #define pb(a) push_back(a)
  30. #define pr(a) cout<<a<<endl
  31. #define pf printf
  32. #define sf scanf
  33. #define swap(a,b) (a ^= b, b ^= a, a ^= b)
  34. #define PI acos(-1)
  35. #define x first
  36. #define y second
  37. #define eps 1e-7
  38.  
  39. typedef int D;
  40. typedef long long int LLD;
  41. typedef unsigned long long int LLU;
  42. typedef vector<D> VI;
  43. typedef set<D> SI;
  44. typedef vector<D>::iterator Viti;
  45.  
  46. /***********Template Ends Here***********/
  47.  
  48. double distance(double x1,double y1,double x2,double y2)
  49. {
  50.     double result=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
  51.     return result;
  52. }
  53.  
  54. int main()
  55. {
  56.     int T,N,i,I,j,k,l;
  57.     double maxx=0,x1,y1,x2,y2,cross1,cross2,dis,dis1,dis2,dis3,dis4;
  58.     pair<double,double>P;
  59.     cin>>T;
  60.     while(T--)
  61.     {
  62.         cin>>N;
  63.         vector<pair<double,double> >V;
  64.         for(i=0; i<N; i++)
  65.         {
  66.             cin>>P.x>>P.y;
  67.             V.pb(P);
  68.         }
  69.         maxx=0;
  70.         if(N>4)
  71.         {
  72.             for(i=0; i<N; i++)
  73.             {
  74.                 for(j=i+1; j<N; j++)
  75.                 {
  76.                     dis=distance(V[i].x,V[i].y,V[j].x,V[j].y);
  77.                     maxx=MAX(dis,maxx);
  78.                 }
  79.             }
  80.         }
  81.         else
  82.         {
  83.             for(i=0; i<N; i++)
  84.             {
  85.                 for(j=0; j<N; j++)
  86.                 {
  87.                     for(k=0; k<N; k++)
  88.                     {
  89.                         for(l=0; l<N; l++)
  90.                         {
  91.                             if(i==j||i==k||i==l||j==k||j==l||k==l)
  92.                                 continue;
  93.                             x1=V[j].x-V[i].x;
  94.                             y1=V[j].y-V[i].y;
  95.                             x2=V[k].x-V[i].x;
  96.                             y2=V[k].y-V[i].y;
  97.                             cross1=x1*y2-x2*y1;
  98.                             x1=V[k].x-V[i].x;
  99.                             y1=V[k].y-V[i].y;
  100.                             x2=V[l].x-V[i].x;
  101.                             y2=V[l].y-V[i].y;
  102.                             cross2=x1*y2-x2*y1;
  103.                             if((cross1<0 && cross2<0)||(cross1>0 && cross2>0))
  104.                             {
  105.                                 dis1=distance(V[i].x,V[i].y,V[j].x,V[j].y);
  106.                                 dis2=distance(V[j].x,V[j].y,V[k].x,V[k].y);
  107.                                 dis3=distance(V[k].x,V[k].y,V[l].x,V[l].y);
  108.                                 dis4=distance(V[i].x,V[i].y,V[l].x,V[l].y);
  109.                                 dis=MAX(MAX(dis1,dis2),MAX(dis3,dis4));
  110.                                 maxx=MAX(maxx,dis);
  111.                             }
  112.                         }
  113.  
  114.                     }
  115.                 }
  116.             }
  117.         }
  118.         printf("%.10lf\n",maxx);
  119.     }
  120.     return 0;
  121. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement