Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // implementare: Cristi Dospra
- // punctaj: 100p
- // complexitate: O(NlogN)
- #include <fstream>
- #include <algorithm>
- #include <cmath>
- #include <iomanip>
- using namespace std;
- #define NMAX 100002
- ifstream fin("archpsod.in");
- ofstream fout("archpsod.out");
- struct point {
- int x, y;
- };
- point v[NMAX];
- inline int sqr(int x) {
- return x * x;
- }
- inline double dist(point A, point B) {
- return sqrt(1.0 * (sqr(A.x - B.x) + sqr(A.y - B.y)));
- }
- point Hull[NMAX];
- inline int det(point A, point B, point C) {
- return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
- }
- int MakeHull(int N) {
- int L = 0;
- for (int i = 1; i <= N; ++i) {
- while (L > 1 && det(Hull[L-1], Hull[L], v[i]) <= 0)
- L--;
- Hull[++L] = v[i];
- }
- int l = L;
- for (int i = N; i >= 1; --i) {
- while (L > l && det(Hull[L-1], Hull[L], v[i]) <= 0)
- L--;
- Hull[++L] = v[i];
- }
- L--;
- return L;
- }
- inline bool cmp(point A, point B) {
- if (A.x == B.x)
- return A.y < B.y;
- return A.x < B.x;
- }
- int main() {
- int N;
- fin >> N;
- for (int i = 1; i <= N; ++i)
- fin >> v[i].x >> v[i].y;
- sort(v + 1, v + N + 1, cmp);
- int T = MakeHull(N);
- double Sol = 0.0;
- for (int i = 1; i <= T; ++i)
- for (int j = i + 1; j <= T; ++j)
- Sol = max(Sol, dist(Hull[i], Hull[j]));
- fout << fixed << setprecision(6) << Sol << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement