显然当你把枚举边换成枚举点时,点对距离不是单峰的。直接交有92分,在sub0的第一个点WA了。
如下hack数据就卡掉了枚举点的做法:
9
-78 97
-77 87
-69 11
-52 -100
94 45
75 68
65 74
22 98
-5 98
代码:
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=2e5+5;
const db eps=1e-8;
using ll=long long;
int n;
inline int sgn(db x){
if(fabs(x)<=eps)return 0;
return x>0?1:-1;
}
struct Point{
db x,y;
Point operator +(const Point B){return {x+B.x,y+B.y};}
Point operator -(const Point B){return {x-B.x,y-B.y};}
bool operator ==(const Point B){return !sgn(x-B.x)&&!sgn(y-B.y);}
bool operator <(const Point B){
return sgn(x-B.x)<0||(!sgn(x-B.x)&&sgn(y-B.y)<0);
}
}a[N],qu[N];
typedef Point Vector;
inline db Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}
inline db squ(db x){return x*x;}
inline db dis(Point A,Point B){return sqrt(squ(A.x-B.x)+squ(A.y-B.y));}
inline int pdis(Point A,Point B){return squ(A.x-B.x)+squ(A.y-B.y);}
int tl;
inline void Convex(){
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
while(tl>1&&Cross(qu[tl]-qu[tl-1],a[i]-qu[tl])<=0)tl--;
qu[++tl]=a[i];
}
int cur=tl;
for(int i=n-1;i>=1;i--){
while(tl>cur&&Cross(qu[tl]-qu[tl-1],a[i]-qu[tl])<=0)tl--;
qu[++tl]=a[i];
}
if(n>1)tl--;
}
int nxt[N];
inline db len(Vector A){return sqrt(squ(A.x)+squ(A.y));}
struct Line{
Point A;Vector B;
};
inline db PTL(Point P,Line Q){
Vector p1=P-Q.A,p2=Q.B;
return fabs(Cross(p1,p2))/len(p2);
}
int ans;
int pre[N];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
Convex();
for(int i=1;i<=tl;i++)nxt[i]=i%tl+1;
// if(tl>5)assert(0);
if(tl==2){
cout<<pdis(qu[1],qu[2])<<"\n";
return 0;
}
else{
int cur=2;
for(int i=1;i<=tl;i++){
while(pdis(qu[cur],qu[i])<=pdis(qu[nxt[cur]],qu[i]))cur=nxt[cur];
ans=max(ans,pdis(qu[i],qu[cur]));
}
cout<<ans;
}
return 0;
}
那么,是否枚举点一定不可行呢,有改进的措施吗?