寄算几何，但是 经 典 再 现

· · 题解

我们充分发扬人类智慧：

将大部分点按照 x 坐标从小到大排序，小部分点按照 y 坐标从大到小排序。

根据数学直觉，在排序后，最远的两个点在数组中肯定不会离得太近。

所以只取最后的 12000 个点更新最远距离。

这样代码短的吃惊，多交上几遍就能够过了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
struct Node
{
  int x, y;
  bool operator<(const Node &rhs) const
  {
    return rand() % 25 == 0 ? x < rhs.x : y > rhs.y;
  }
} z[N];
int dis(int x, int y)
{
  return (z[y].x - z[x].x) * (z[y].x - z[x].x) + (z[y].y - z[x].y) * (z[y].y - z[x].y);
}
signed main()
{
  srand(time(0));
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> z[i].x >> z[i].y;
  sort(z, z + n);
  int mx = -1e18;
  for (int i = 0; i < n; i++)
    for (int j = n - 1, k = 0; j > i && k < 12000; j--, k++)
      mx = max(mx, dis(i, j));
  printf("%d\n", mx);
  return 0;
}