POJ2187 Beauty Contest <旋转卡壳>

Problem

Beauty Contest

Description

贝茜在牛的选美比赛中赢得了冠军”牛世界小姐”。因此,贝西会参观$N$($2\le N\le 50000$)个农场来传播善意。世界将被表示成一个二维平面,每个农场位于一对整数坐标$(x,y)$($-10000\le x,y \le 10000$)。没有两个农场共享相同的一对坐标。
尽管贝西沿直线前往下一个农场，但牧场之间的距离可能很大,所以她需要一个手提箱保证在每一段旅程中她有足够吃的食物。她想确定她可能需要旅行的最大可能距离,她要知道她必须带的手提箱的大小。帮助贝西计算农场的最大距离。

Input

第$1$行一个整数$n$，第$2\sim n+1$行两个整数$x_i\ y_i$表示$n$个农场中第$i$个的坐标

Output

一行，最远距离的平方

Sample Input

4
0 0
0 1
1 1
1 0

Sample Output

2

标签：旋转卡壳

Solution

平面最远点对。
旋转卡壳模板。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 50000
using namespace std;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m;
struct pnt {
    int x, y;
    int operator * (const pnt &t) const {return x*t.y-y*t.x;}
    pnt operator - (const pnt &t) const {return (pnt){x-t.x, y-t.y};}
    bool operator < (const pnt &t) const {return x == t.x ? y < t.y : x < t.x;}
} p[MAX_N+5], c[MAX_N+5];
int sqr(int x) {return x*x;}
int dis(pnt a, pnt b) {return sqr(a.x-b.x)+sqr(a.y-b.y);}
void ConvexHull() {
    sort(p+1, p+n+1), c[++m] = p[1], c[++m] = p[2];
    for (int i = 3; i <= n; c[++m] = p[i++])
        while (m > 1 && (p[i]-c[m-1])*(c[m]-c[m-1]) >= 0) m--;
    int t = m;	c[++m] = p[n-1];
    for (int i = n-2; i; c[++m] = p[i--])
        while (m > t && (p[i]-c[m-1])*(c[m]-c[m-1]) >= 0) m--;
    m--;
}
int RotatingCalipers() {
    if (m == 2) return dis(c[1], c[2]);	int a = 1, b = 1;
    for (int i = 1; i <= m; i++) if (c[i] < c[a]) a = i;
    for (int i = 1; i <= m; i++) if (c[b] < c[i]) b = i;
    int ret = dis(c[a], c[b]);
    for (int sa = a, sb = b; a^sb || b^sa; ret = max(ret, dis(c[a], c[b])))
        (c[a%m+1]-c[a])*(c[b%m+1]-c[b]) <= 0 ? a = a%m+1 : b = b%m+1;
    return ret;
}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(p[i].x), read(p[i].y);
    return ConvexHull(), printf("%d", RotatingCalipers()), 0;
}