这东西学了我大概两天吧。。其实不应该学这么久的，但是这两天有点小困，然后学习时间被削了很多\(QwQ\)
说几个坑点。
- 对于题目不保证有凸包的情况，要选用左下角的点，而非单纯的最下边的点构造凸包。
- 对于凸包中只有\(1/2\)个点的情况，要注意特殊判断。
算法流程就比较简单了。先构造一个凸包，然后利用对踵点都是逆时针跑（类似于两把尺子卡着凸包转）的原理，每次判断到当前直线距离最远的点，更新当前对踵点即可。
例题 【luogu P1452】Beauty contest
#include <bits/stdc++.h>
#define N 50010
using namespace std;struct point {int x, y;
}arr[N], hull[N];int n, top;int cross (point u1, point u2, point v1, point v2) {return (u2.x - u1.x) * (v2.y - v1.y) - (u2.y - u1.y) * (v2.x - v1.x);
}int point_dis (point u, point v) {return (v.x - u.x) * (v.x - u.x) + (v.y - u.y) * (v.y - u.y);
}bool cmp (point lhs, point rhs) {if (cross (arr[1], lhs, arr[1], rhs) < 0) return false;if (cross (arr[1], lhs, arr[1], rhs) > 0) return true;return point_dis (arr[1], lhs) < point_dis (arr[1], rhs);
}void get_hull () {sort (arr + 2, arr + 1 + n, cmp);hull[++top] = arr[1];for (int i = 2; i <= n; ++i) {while (top > 1 && cross (hull[top - 1], hull[top], hull[top], arr[i]) <= 0) --top;hull[++top] = arr[i];}hull[top + 1] = arr[1];
}int get_ans () {if (top == 1) return 0;if (top == 2) return point_dis (hull[1], hull[2]);int v = 2, ans = 0;for (int u = 1; u <= top; ++u) {while (cross (hull[u], hull[u + 1], hull[u + 1], hull[v]) <=cross (hull[u], hull[u + 1], hull[u + 1], hull[v + 1])) {v = v == top ? 1 : v + 1;}ans = max (ans, max (point_dis (hull[u], hull[v]), point_dis (hull[u + 1], hull[v])));}return ans;
}int main () {cin >> n;for (int i = 1; i <= n; ++i) {cin >> arr[i].x >> arr[i].y;if (arr[i].y < arr[1].y || (arr[i].y == arr[1].y && arr[i].x < arr[1].x)) {swap (arr[i], arr[1]);}}get_hull ();cout << get_ans () << endl;
}
