发现了亿点错,现在多对了一个点。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 50000 + 10;
int n, idx = -1, tot;
struct node{
double x, y;
} p[N];
node st[N];
double getcro(node p1, node q1, node p2, node q2){
return (q1.x - p1.x) * (q2.y - p2.y) - (q2.x - p2.x) * (q1.y - p1.y);
}
double dis(node p1, node p2){
return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
}
bool cmp(node a, node b){
double now = getcro(p[1], a, p[1], b);
if(now > 0 || (now == 0 && dis(p[1], a) < dis(p[1], b)))
return 1;
return 0;
}
double rotate(){
int j = 1;
double ans = 0;
for(int i=1;i<tot;i++){
while(getcro(st[i], st[i + 1], st[i], st[j]) < getcro(st[i], st[i + 1], st[i], st[j + 1]))
j = (j + 1) % tot;//只要是上升的,一直逆时针转,看谁先撑不住
// cout << st[i].x << ' ' << st[i].y << ',' << st[i + 1].x << ' ' << st[i + 1].y << ',' << st[j].x << ' ' << st[j].y << endl;
ans = max(ans, max(dis(st[i], st[j]), dis(st[i + 1], st[j])));
}
return ans;
}
int main(){
scanf("%d", &n);
for(int i=1;i<=n;i++){
scanf("%lf%lf", &p[i].x, &p[i].y);
if(idx == -1 || p[i].y < p[idx].y || (p[i].y == p[idx].y && p[i].x < p[idx].x))
idx = i;
}
swap(p[1], p[idx]);
sort(p + 2, p + n + 1, cmp);
st[++tot] = p[1];
for(int i=2;i<=n;i++){
while(tot > 1 && getcro(st[tot - 1], st[tot], st[tot], p[i]) <= 0)
--tot;
st[++tot] = p[i];
}
printf("%.0lf\n", rotate());
return 0;
}
```
by chlchl @ 2023-01-12 13:07:14
草,漏了条边,AC 了。
by chlchl @ 2023-01-12 13:10:19
@[caihaolang](/user/363036) 这题的算分如下:
Sub#0:$0,8,8,8,8,8,8,8,8,9,9,9,9$,总和 $100$。
Sub#1:$0,0,0,0,0$,总和同样为 $100$。
你这算水 $100$ 分……
by LittleAcbg @ 2023-01-12 13:38:02
@[LuoJingjia](/user/531709) 阿哲,恐怖的。
by chlchl @ 2023-01-12 14:06:53