verify/geometry/aoj-cgl-4-b.test.cpp

View this file on GitHub
Last update: 2024-08-11 09:50:12+00:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_B

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_B"
#define ERROR 0.000001

#define main main2
#include "../../contest/template.cpp"
#undef main

#include "../../geometry/Point.cpp"
#include "../../geometry/Hull.cpp"
#include "../../geometry/Diameter.cpp"

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.precision(20), cout.setf(ios::fixed);

    int n;
    cin >> n;
    vector<vec> arr(n);
    for (auto &el : arr) {
        cin >> el.x >> el.y;
    }
    cout << diameter(arr) << '\n';
}

#line 1 "verify/geometry/aoj-cgl-4-b.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_B"
#define ERROR 0.000001

#define main main2
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define pbc push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define vin(v) for (auto &el : a) cin >> el

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 &y) {
    if (y < x) {
        x = y;
    }
}

template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 &y) {
    if (x < y) {
        x = y;
    }
}

void solve() {
    
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.precision(20), cout.setf(ios::fixed);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
#line 6 "verify/geometry/aoj-cgl-4-b.test.cpp"
#undef main

#line 1 "geometry/Point.cpp"
/**
 * Author: alexxela12345,daubi,talant
 * Date: 2024-08-03
 * Description: struct Point
 */

const ld EPS = 1e-7;

ld sq(ld x) {
    return x * x;
}

int sign(ld x) {
    if (x < -EPS) {
        return -1;
    }
    if (x > EPS) {
        return 1;
    }
    return 0;
}

#define vec point
struct point {//% - cross, * - dot
    ld x, y;
    auto operator<=>(const point&) const = default;
};
ld operator*(const point &a, const point &b) {
    return a.x * b.x + a.y * b.y;
}
ld operator%(const point &a, const point &b) {
    return a.x * b.y - a.y * b.x;
}
point operator-(const point &a, const point &b) {
    return {a.x - b.x, a.y - b.y};
}
point operator+(const point &a, const point &b) {
    return {a.x + b.x, a.y + b.y};
}
point operator*(const point &a, ld b) {
    return {a.x * b, a.y * b};
}
point operator/(const point &a, ld b) {
    return {a.x / b, a.y / b};
}
bool operator<(const point &a, const point &b)  {
    if (sign(a.y - b.y) != 0) {
        return a.y < b.y;
    } else if (sign(a.x - b.x) != 0) {
        return a.x < b.x;
    }
    return 0;
}
ld len2(const point &a) {
    return sq(a.x) + sq(a.y);
}
ld len(const point &a) {
    return sqrt(len2(a));
}
point norm(point a) {
    return a / len(a);
}
int half(point a) {
    return (sign(a.y) == -1 || (sign(a.y) ==0 && a.x < 0));
}
point ort(point a) {
    return {-a.y, a.x};
}
point turn(point a, ld ang) {
    return {a.x * cos(ang) - a.y * sin(ang), a.x * sin(ang) + a.y * cos(ang)};
}
ld getAngle(point &a, point &b) {
    return atan2(a % b, a * b);
}
bool cmpHalf(const point &a, const point &b) {
    if (half(a) != half(b)) {
        return half(b);
    } else {
        int sgn = sign(a % b);
        if (!sgn) {
            return len2(a) < len2(b);
        } else {
            return sgn == 1;
        }
    }
}
#line 1 "geometry/Hull.cpp"
/**
 * Author: alexxela12345,daubi,talant
 * Date: 2024-08-03
 * Description: Polygon functions
 */

vector<point> hull(vector<point> p, bool need_all=false) {
   sort(all(p));
   p.erase(unique(all(p)), end(p));
   int n = p.size(), k = 0;
   if (n <= 2) return p;
   vector<point> ch(2 * n);
   ld th = need_all ? -EPS : +EPS; // 0 : 1 if int
   for (int i = 0; i < n; ch[k++] = p[i++]) {
     while (k >= 2 && (ch[k - 1] - ch[k - 2]) % (p[i] - ch[k - 1]) < th) --k;
   }
   for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
     while (k >= t && (ch[k - 1] - ch[k - 2]) % (p[i] - ch[k - 1]) < th) --k;
   }
   ch.resize(k - 1);
   return ch;
 }
#line 1 "geometry/Diameter.cpp"
/**
 * Author: Igor Markelov
 * Date: 2022-11-18
 * Description: Rotating calipers.
 * Time: O(n)
 */

ld diameter(vector<point> p) {
    p = hull(p);
    int n = p.size();
    if (n <= 1) {
        return 0;
    }
    if (n == 2) {
        return len(p[0] - p[1]);
    }
    ld ans = 0;
    int i = 0, j = 1;
    while (i < n) {
        while (sign((p[(i + 1) % n] - p[i]) % (p[(j + 1) % n] - p[j])) >= 0) {
            chkmax(ans, len(p[i] - p[j]));
            j = (j + 1) % n;
        }
        chkmax(ans, len(p[i] - p[j]));
        ++i;
    }
    return ans;
}
#line 11 "verify/geometry/aoj-cgl-4-b.test.cpp"

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.precision(20), cout.setf(ios::fixed);

    int n;
    cin >> n;
    vector<vec> arr(n);
    for (auto &el : arr) {
        cin >> el.x >> el.y;
    }
    cout << diameter(arr) << '\n';
}