fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct point {
  6.     long long x;
  7.     long long y;
  8.     point (long long nx = 0, long long ny = 0): x(nx), y(ny) {
  9.     }
  10.     bool operator< (const point &p) const {
  11.         return x < p.x || (x == p.x && y < p.y);
  12.     }
  13.     bool operator== (const point &p) const {
  14.         return x == p.x && y == p.y;
  15.     }
  16. };
  17. bool clockwise (point a, point b, point c) {
  18.     return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) < 0;
  19. }
  20.  
  21. bool counter_clockwise (point a, point b, point c) {
  22.     return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)) > 0;
  23. }
  24.  
  25. long long distance (const point &a, const point &b) {
  26.     return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
  27. }
  28.  
  29. int main () {
  30.     int N;
  31.     cin >> N;
  32.     vector<point> a(0);
  33.     for (int i = 0; i < N; i++) {
  34.         long long x, y;
  35.         cin >> x >> y;
  36.         a.emplace_back(x,y);
  37.     }
  38.     sort(a.begin(), a.end());
  39.     if (a[0] == a[N - 1]) {
  40.         cout << 0;
  41.         return 0;
  42.     }
  43.  
  44.     point left = a[0];
  45.     point right = a[N-1];
  46.     vector <point> top(0);
  47.     top.push_back(left);
  48.     vector <point> lower(0);
  49.     lower.push_back(left);
  50.     for (int i = 1; i < N; i++) {
  51.         if (i == N - 1 || counter_clockwise(left, a[i], right)) {
  52.             while (!counter_clockwise(lower[lower.size() - 2], lower[lower.size() - 1], a[i]) && lower.size() >= 2 ) {
  53.                 lower.pop_back();
  54.             }
  55.             lower.push_back(a[i]);
  56.         }
  57.         if (i == N - 1 || clockwise(left, a[i], right)) {
  58.             while (top.size() >= 2 && !clockwise(top[top.size() - 2], top[top.size() - 1], a[i])) {
  59.                 top.pop_back();
  60.             }
  61.             top.push_back(a[i]);
  62.         }
  63.     }
  64.     vector<point> ans(0);
  65.     for (auto i : top) {
  66.         ans.push_back(i);
  67.     }
  68.     for (int i = lower.size() - 2; i > 0; --i) {
  69.         ans.push_back(lower[i]);
  70.     }
  71.     long long diam = 0;
  72.     for (int i = 0, j = 1; i < ans.size(); i++) {
  73.         while ((j < ans.size() - 1)  && (distance(ans[i],ans[j]) <= distance(ans[i],ans[j+1])) ){
  74.             j++;
  75.         }
  76.         diam = max(diam, distance(ans[i], ans[j]));
  77.     }
  78.     cout << fixed << setprecision(20);
  79.     cout << sqrt(diam);
  80.     return 0;
  81. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
0 0
2 2
1 1
0 2
2 0
stdout
copy 
2.82842712474619029095
https://ideone.com/XP3HyU
language:
C++14 (gcc 8.3)
created:
1 hour 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!