周游世界问题

解题思路：

本题要求平面上所有点中最远点对的距离，就是一个旋转卡壳的模板题。

旋转卡壳相关概念

二维凸包相关概念

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n;
PII q[N]; //存储所有点的坐标
int stk[N], top; //栈，存储凸包
bool st[N]; //记录每个点是否在凸包中

PII operator-(PII a, PII b) //重载向量减法
{
    return {a.x - b.x, a.y - b.y};
}

int operator*(PII a, PII b) //重载叉乘
{
    return a.x * b.y - a.y * b.x;
}

int area(PII a, PII b, PII c) //求 ab 和 ac 构成的平行四边形的有向面积
{
    return (b - a) * (c - a);
}

int get_dist(PII a, PII b) //求 a 和 b 的距离的平方
{
    int x = a.x - b.x, y = a.y - b.y;
    return x * x + y * y;
}

void andrew() //求二维凸包
{
    sort(q, q + n); //将所有点按照横、纵坐标从小到大排序

    //求下凸包
    for(int i = 0; i < n; i++)
    {
        //不保留直线上的点
        while(top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) <= 0)
            if(area(q[stk[top - 2]], q[stk[top - 1]], q[i]) < 0) st[stk[--top]] = false;
            else top--; //如果点在直线上则不重置标记
        stk[top++] = i;
        st[i] = true;
    }

    //求上凸包
    st[0] = false; //将起点的标记重置
    for(int i = n - 1; i >= 0; i--)
    {
        if(st[i]) continue; //如果当前点已经在凸包中，直接跳过
        while(top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) <= 0) top--;
        stk[top++] = i;
    }
    top--; //起点加入了两次，删掉一次
}

int rotating_calipers() //旋转卡壳求最远点对的距离，并返回距离的平方
{
    if(top < 2) return get_dist(q[0], q[n - 1]); //如果多点共线，则他们之间的距离就是答案
    int res = 0; //记录最远距离
    for(int i = 0, j = 2; i < top; i++)
    {
        PII a = q[stk[i]], b = q[stk[i + 1]];
        while(area(a, b, q[stk[j]]) < area(a, b, q[stk[j + 1]])) j = (j + 1) % top; //找出距离当前边最远的点
        res = max(res, max(get_dist(a, q[stk[j]]), get_dist(b, q[stk[j]]))); //更新答案
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d%d", &q[i].x, &q[i].y);

    andrew(); //求二维凸包
    printf("%d\n", rotating_calipers()); //旋转卡壳求最远点对的距离

    return 0;
}