# Untitled

unknown
c_cpp
a year ago
2.1 kB
3
Indexable
Never
```#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#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 used[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) {
return (b - a) * (c - a);
}

int get_dist(PII a, PII b) {
int dx = a.x - b.x, dy = a.y - b.y;
return dx * dx + dy * dy;
}

void get_convex() {

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)
used[stk[--top]] = false;  // 注意: --top
else top--;
}
stk[top++] = i;
used[i] = true;
}

used[0] = false;
for (int i = n - 1; i >= 0; i--) {
if (used[i]) continue;

while (top >= 2 && area(q[stk[top - 2]], q[stk[top - 1]], q[i]) <= 0)
top--;
stk[top++] = i;
}

top--;  // 让top指向最后一个有用点
}

// 返回最远的两个点距离的平方
int rotating_calipers() {

if (top <= 1) return get_dist(q[0], q[n - 1]);  // 凸包上只有两个点

int res = 0;
for (int i = 0, j = 2; i < top; i++) {  // 双指针算法
auto d = q[stk[i]], e = q[stk[i + 1]];  // 枚举的边
// 找到距离边de最远的点
while (area(d, e, q[stk[j]]) < area(d, e, q[stk[j + 1]])) j = (j + 1) % top;
res = max(res, max(get_dist(d, q[stk[j]]), get_dist(e, 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);

get_convex();

printf("%d\n", rotating_calipers());

return 0;
}
```