20230332fuben @ 2024-01-04 23:01:52
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long double ld;
int n,cnt=0;
struct inf
{
ld x,y;
}node[200020],t[200020],tem[200020];
ld dis(ld x1,ld y1,ld x2,ld y2)
{ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
bool cmp(inf i,inf j)
{
if(i.x!=j.x)return i.x<j.x;
else return i.y<j.y;
}
bool cmpy(inf i,inf j)
{
return i.y<j.y;
}
void merge(int l,int r)
{
if(l==r)return ;
int mid=(l+r)>>1;
merge(l,mid),merge(mid+1,r);
for(int a=l,i=l,j=mid+1;a<=r;a++)
{
if(j==r+1) tem[a]=node[i++];
else if(i==mid+1) tem[a]=node[j++];
else
{
if(node[i].x!=node[j].x)
{
if(node[i].x<node[j].x)tem[a]=node[i++];
else tem[a]=node[j++];
}
else
{
if(node[i].y<node[j].y)tem[a]=node[i++];
else tem[a]=node[j++];
}
}
}
for(int a=l;a<=r;a++)node[a]=tem[a];
}
void mergesort(int l,int r)
{
if(l==r)return ;
int mid=(l+r)>>1;
mergesort(l,mid),mergesort(mid+1,r);
for(int a=l,i=l,j=mid+1;a<=r;a++)
{
if(j==r+1) tem[a]=t[i++];
else if(i==mid+1) tem[a]=t[j++];
else
{
if(node[i].y<node[j].y) tem[a]=t[i++]; //这里
// if(t[i].y<t[j].y) tem[a]=t[i++];
else tem[a]=t[j++];
}
}
for(int a=l;a<=r;a++)t[a]=tem[a];
}
ld solve(int l,int r)
{
if(l==r)return 2099999999.9;
if(l+1==r)return dis(node[l].x,node[l].y,node[r].x,node[r].y);
int mid=(l+r)>>1,cnt=1;
ld d=min(solve(l,mid),solve(mid+1,r));
for(int a=l;a<=r;a++)
if(fabs(node[a].x-node[mid].x)<d) t[cnt++]=node[a];
mergesort(0,cnt-1);
for(int a=0;a<cnt-1;a++)
for(int b=a+1;b<cnt&&fabs(t[b].y-t[a].y)<d;b++)
d=min(d,dis(t[a].x,t[a].y,t[b].x,t[b].y));
cnt=0;
return d;
}
int main(void)
{
scanf("%d",&n);
for(int a=1;a<=n;a++)
scanf("%Lf%Lf",&node[a].x,&node[a].y);
merge(1,n);
cout.setf(ios_base::fixed);
cout.precision(4);
cout<<solve(1,n);
return 0;
}
第60行(标记处)那里我是给t数组归并,写成了node,居然过了,反应过来我就改成t,改成正确的居然过不了!!!!大佬们为什么