fork download
copy 
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. typedef long double Coordinate; // for int change it to long long
  10. struct Point
  11. {
  12.     Coordinate x, y;
  13.     Coordinate length2()const{return x*x + y*y;}
  14.     long double length()const{return sqrt((long double)length2());}
  15. };
  16. struct CompareX
  17. {
  18.     bool operator () (const Point &a, const Point &b) const
  19.     {
  20.         return a.x < b.x || (a.x == b.x && a.y < b.y);
  21.     }
  22. };
  23. typedef vector<Point> Poligonal;
  24.  
  25. const Coordinate EPS = 1e-15; // for int change it to 0
  26.  
  27. Point operator - (const Point &a, const Point &b) { return {a.x - b.x, a.y - b.y}; }
  28. Coordinate operator * (const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; } /*cross*/
  29. Coordinate operator ^ (const Point &a, const Point &b) { return a.x * b.x + a.y * b.y; } /*dot*/
  30.  
  31. /*CW*/
  32. inline Poligonal getConvexHull(Poligonal poligonial)
  33. {
  34.     sort(poligonial.begin(), poligonial.end(), CompareX());
  35.  
  36.     Poligonal upperConvexHull, lowerConvexHull;
  37.  
  38.     for (const Point &point : poligonial)
  39.     {
  40.         while (upperConvexHull.size() >= 2 &&
  41.                (point - upperConvexHull[upperConvexHull.size()-2]) *
  42.                (upperConvexHull[upperConvexHull.size()-1] - upperConvexHull[upperConvexHull.size()-2]) <= EPS)
  43.         {
  44.             upperConvexHull.pop_back();
  45.         }
  46.         upperConvexHull.push_back(point);
  47.  
  48.         while (lowerConvexHull.size() >= 2 &&
  49.                (point - lowerConvexHull[lowerConvexHull.size()-2]) *
  50.                (lowerConvexHull[lowerConvexHull.size()-1] - lowerConvexHull[lowerConvexHull.size()-2]) >= -EPS)
  51.         {
  52.             lowerConvexHull.pop_back();
  53.         }
  54.         lowerConvexHull.push_back(point);
  55.     }
  56.  
  57.     upperConvexHull.insert(upperConvexHull.end(), lowerConvexHull.rbegin()+1, lowerConvexHull.rend()-1);
  58.  
  59.     return upperConvexHull;
  60. }
  61.  
  62. vector < pair < Point, Point > > getAntipodalPairs(Poligonal poligonal)
  63. {
  64.     poligonal = getConvexHull(poligonal);
  65.     vector < pair < Point, Point > > antipodalPairs;
  66.  
  67.     int i = 0, j = 1;
  68.  
  69.     while(
  70.           ((poligonal[(j+1) % poligonal.size()] - poligonal[j]) * (poligonal[i+1] - poligonal[i])) > EPS &&
  71.           ((poligonal[(j+1) % poligonal.size()] - poligonal[j]) ^ (poligonal[i+1] - poligonal[i])) > EPS
  72.     )
  73.     {
  74.         j = (j+1) % poligonal.size();
  75.     }
  76.  
  77.     antipodalPairs.emplace_back(poligonal[i], poligonal[j]);
  78.  
  79.     int current = i;
  80.  
  81.     while(j + 1 < poligonal.size())
  82.     {
  83.         Point currentVector = poligonal[(current+1)%poligonal.size()] - poligonal[current];
  84.         Point iVector = poligonal[(i+1)%poligonal.size()] - poligonal[i];
  85.         Point jVector = poligonal[j+1] - poligonal[j];
  86.  
  87.         if (currentVector * iVector < currentVector * jVector ||
  88.             abs(currentVector * jVector - currentVector * iVector) <= EPS)
  89.         {
  90.             i = (i+1) % poligonal.size();
  91.             current = i;
  92.         }
  93.         else
  94.         {
  95.             ++j;
  96.             current = j;
  97.         }
  98.  
  99.         antipodalPairs.emplace_back(poligonal[i], poligonal[j]);
  100.  
  101.         currentVector = poligonal[(current+1)%poligonal.size()] - poligonal[current];
  102.         iVector = poligonal[(i+1)%poligonal.size()] - poligonal[i];
  103.         jVector = poligonal[j+1] - poligonal[j];
  104.  
  105.         if (abs(currentVector * iVector - currentVector * jVector) <= EPS)
  106.         {
  107.             antipodalPairs.emplace_back(poligonal[(i+1)%poligonal.size()], poligonal[j]);
  108.             antipodalPairs.emplace_back(poligonal[(i+1)%poligonal.size()], poligonal[j+1]);
  109.             antipodalPairs.emplace_back(poligonal[i], poligonal[j+1]);
  110.  
  111.             if (current == i)
  112.             {
  113.                 ++j;
  114.             }
  115.             else
  116.             {
  117.                 i = (i+1) % poligonal.size();
  118.             }
  119.         }
  120.  
  121.     }
  122.  
  123.  
  124.     return antipodalPairs;
  125. }
  126.  
  127. vector < pair < Point, Point > > getAntipodalPairs2(Poligonal poligonal)
  128. {
  129.     poligonal = getConvexHull(poligonal);
  130.     vector < pair < Point, Point > > antipodalPairs;
  131.     int j = 0;
  132.  
  133.     for (int i = 0; i < (int)poligonal.size(); ++i)
  134.     {
  135.         while ((poligonal[i] - poligonal[j]).length2() <= (poligonal[i] - poligonal[(j + 1) % (int)poligonal.size()]).length2() && i != (j + 1) % (int)poligonal.size()) {
  136.             j = (j + 1) % (int)poligonal.size();
  137.         }
  138.  
  139.         antipodalPairs.emplace_back(poligonal[i], poligonal[j]);
  140.     }
  141.  
  142.     return antipodalPairs;
  143. }
  144.  
  145. inline void kattis_roberthood()
  146. {
  147.     int c;
  148.  
  149.     while (~scanf("%d", &c))
  150.     {
  151.         Poligonal shots(c);
  152.  
  153.         for (int i = 0; i < c; ++i)
  154.         {
  155.             scanf("%Lf%Lf", &shots[i].x, &shots[i].y);
  156.         }
  157.  
  158.         auto antipodalPairs = getAntipodalPairs2(shots);
  159.  
  160.         long double answer = 0.0L;
  161.         for (const auto &antipodalPair : antipodalPairs)
  162.         {
  163.             answer = max(answer, (antipodalPair.first - antipodalPair.second).length());
  164.         }
  165.  
  166.         printf("%.8Lf\n", answer);
  167.     }
  168. }
  169.  
  170. int main()
  171. {
  172.     kattis_roberthood();
  173.  
  174.     return 0;
  175. }
  176.  
Success #stdin #stdout 0s 4572KB
comments (?)
stdin
copy 
2
2 2
-1 -2
5
-4 1
-100 0
0 4
2 -3
2 300
stdout
copy 
5.00000000
316.86590224
https://ideone.com/FxjD9D
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!