w_II_j @ 2022-08-12 20:32:00
然后改为merg(l,mid-1)又WA了另一个不同的点; 下方为91分代码,与82分的差距仅在于18,19行
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
struct point{
double x;
double y;
}p[MAXN];int temp[MAXN];bool cmp(point a,point b){return a.x<b.x;}
double len(int a,int b)
{
return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
int n;double dis;
double merg(int l,int r)
{
if(l==r)return 1<<28;
if(l==r-1)return len(l,r);
int mid=(l-r)/2+r;
double a=merg(l,mid-1);
double b=merg(mid,r);
dis=min(a,b);
int k=0;
for(int i=l;i<=r;i++)
{
if(fabs(p[i].x-p[mid].x)<=dis){
temp[++k]=i;
}
}
for(int i=1;i<=k;i++){
for(int j=i+1;j<=k&&fabs(p[temp[i]].y-p[temp[j]].y);j++)
dis=min(dis,len(temp[i],temp[j]));
}return dis;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
sort(p+1,p+1+n,cmp);
cout<<fixed<<setprecision(4)<<merg(1,n);
return 0;
}
下方为82分代码(真的别的地方都一样)
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
struct point{
double x;
double y;
}p[MAXN];int temp[MAXN];bool cmp(point a,point b){return a.x<b.x;}
double len(int a,int b)
{
return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
int n;double dis;
double merg(int l,int r)
{
if(l==r)return 1<<28;
if(l==r-1)return len(l,r);
int mid=(l-r)/2+r;
double a=merg(l,mid);
double b=merg(mid+1,r);
dis=min(a,b);
int k=0;
for(int i=l;i<=r;i++)
{
if(fabs(p[i].x-p[mid].x)<=dis){
temp[++k]=i;
}
}
for(int i=1;i<=k;i++){
for(int j=i+1;j<=k&&fabs(p[temp[i]].y-p[temp[j]].y);j++)
dis=min(dis,len(temp[i],temp[j]));
}return dis;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
sort(p+1,p+1+n,cmp);
cout<<fixed<<setprecision(4)<<merg(1,n);
return 0;
}
by w_II_j @ 2022-08-12 22:26:18
@hgzxgzx 抱(激动