平面最近最远点对随机法
cpp
pair<double,double> calc(int arg,vector<Point> &p){
int n=p.size();
for(int i=0;i<n;i++){
double x=p[i].x,y=p[i].y;
p[i].x=x*cos(arg)-y*sin(arg);
p[i].y=x*sin(arg)+y*cos(arg);
}
sort(p.begin(),p.end());
static const int S=10,T=10;
double mn=LLONG_MAX,mx=-LLONG_MAX;
for(int i=0;i<n;i++){
for(int j=i+1;j<n&&j<=i+S;j++)mn=min(mn,(p[i]-p[j]).dis());
for(int j=n-1;j>i&&j>=n-T-1;j--)mx=max(mx,(p[i]-p[j]).dis());
}
return {mn,mx};
}
pair<double,double> get(int T,vector<Point> &p){
double mn=LLONG_MAX,mx=-LLONG_MAX;
for(int i=0;i<T;i++){
auto [a,b]=calc(i*PI/T,p);
mn=min(mn,a),mx=max(mx,b);
}
return {mn,mx};
}