题意分析

题目要求找出所有农场中距离最远的两个点，并输出它们距离的平方。每个农场的位置是二维平面上的坐标点，且没有重复坐标。需要注意的是，这里只需要计算距离的平方，不需要开根号，这样能避免浮点运算的复杂性。

解题思路

核心目标：找到所有点中横纵坐标组合后，使得（x 差的平方 + y 差的平方）最大的两个点。

简化思路：最远点对通常出现在坐标的 “边界” 位置，比如 x 最大、x 最小、y 最大、y 最小的点中。因此可以先筛选出这几类极值点，再在其中计算距离平方的最大值。

具体步骤：

遍历所有点，记录 x 的最大值、最小值，y 的最大值、最小值。

取出这 4 个极值对应的点（可能有重复，比如某个点同时是 x 和 y 的极值点）。

计算这些极值点之间所有点对的距离平方，找到其中的最大值。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 50005;
int top,n,start;
int stacks[maxn];//记录凸包中的点
struct Point
{
    int x,y;
}points[maxn];
int maxs(int a,int b)
{
    return a > b ? a : b;
}
int distances(Point a,Point b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int cross(Point p0,Point p1,Point p2)
{
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
bool cmp(Point p1,Point p2)//横坐标从小到大排序
{
 
    if(p1.x != p2.x)
    {
        return p1.x < p2.x;
    }
    else
    {
        return p1.y < p2.y;
    }
}
void andrew(int n)//找凸包O(nlogn)
{
    sort(points,points + n,cmp);
    for(int i = 0;i < n;i++)//下凸包
    {
        while(top >= 2 && cross(points[stacks[top - 2]],points[stacks[top - 1]],points[i]) <= 0)
        {
            top--;
        }
        stacks[top++] = i;//新元素压栈
    }
    int temp = top + 1;
    for(int i = n - 2;i >= 0;i--)//上凸包
    {
        while(top >= temp && cross(points[stacks[top - 2]],points[stacks[top - 1]],points[i]) <= 0)
        {
            top--;
        }
        stacks[top++] = i;
    }
    if(n > 1)
        top--;//因为起点被计算了两次
}
int rotatingCaliper()//旋转卡壳O(n)
{
    int q = 1;
    int ans = 0;
    for(int i = 0;i < top;i++)//凸包上的每一个点
    {
        while(cross(points[stacks[i]],points[stacks[i + 1]],points[stacks[q + 1]]) >
              cross(points[stacks[i]],points[stacks[i + 1]],points[stacks[q]]))
        {
            q = (q + 1) % top;//单峰函数，直到最高点时跳出循环
        }
        int d1 = distances(points[stacks[i]],points[stacks[q]]);
        int d2 = distances(points[stacks[i + 1]],points[stacks[q]]);
        ans = maxs(ans,maxs(d1,d2));//更新最大值
    }
    return ans;
}
 
void init()
{
    top = 0;
    for(int i = 0;i < n;i++)
    {
        scanf("%d %d",&points[i].x,&points[i].y);
    }
}
void solve()
{
    andrew(n);
    int res = rotatingCaliper();
    printf("%d\n",res);
}
int main()
{
    while(scanf("%d",&n) != EOF)
    {
        init();
        solve();
    }
    return 0;
}
```

```