poj2187 Beauty Contest

传送门：http://poj.org/problem?id=2187

【题解】

凸包、卡壳模板

# include <math.h>
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;
const double eps = 1e-8;

# define RG register
# define ST static

int n;

struct P {
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y) {}
    friend P operator + (P a, P b) {
        return P(a.x+b.x, a.y+b.y);
    }
    friend P operator - (P a, P b) {
        return P(a.x-b.x, a.y-b.y);
    }
    friend double operator * (P a, P b) {
        return a.x*b.y - a.y*b.x;
    }
    friend bool operator < (P a, P b) {
        if(fabs(a.y - b.y) < eps) return a.x < b.x;
        else return a.y < b.y;
    }
    inline double dist2() {
        return x*x+y*y;
    }
}p[M];

inline bool cmp(P a, P b) {
    if(fabs((a-p[1])*(b-p[1])) < eps) return (a-p[1]).dist2() < (b-p[1]).dist2();
    return (a-p[1])*(b-p[1]) > 0;
}

P a[M];
int m = 0;
inline void graham() {
    for (int i=2; i<=n; ++i)
        if(p[i] < p[1]) swap(p[i], p[1]);
    sort(p+2, p+n+1, cmp);
    a[++m] = p[1], a[++m] = p[2];
    for (int i=3; i<=n; ++i) {
        while(m >= 2 && (a[m] - a[m-1])*(p[i] - a[m-1]) < eps) --m;
        a[++m] = p[i];
    }    
}

inline void rotating() {
    double ans = 0;
    int r = 2;
    a[m+1] = a[1];
    for (int l=1; l<=m; ++l) {
        while((a[l+1]-a[l])*(a[r]-a[l]) < (a[l+1]-a[l])*(a[r+1]-a[l])) {
            ++r;
            if(r == m+1) r = 1;
        }
        ans = max(ans, (a[r]-a[l]).dist2());
    }
    printf("%d
", (int)ans);
}
int main() {
    cin >> n;
    for (int i=1; i<=n; ++i)
        scanf("%lf%lf", &p[i].x, &p[i].y);
    graham();
    rotating();
    return 0;
}