用的是传统的分治的思想但是就是WA了3个点(104,107,113)呜呜呜呜,希望有大佬救救!
#include <bits/stdc++.h>
using namespace std;
struct point
{
long long x;
long long y;
point(long long x,long long y)
{
this->x=x;
this->y=y;
}
};
bool cmpy(point &a,point&b)
{
return a.y<b.y;
}
bool cmpx(point &a,point &b)
{
return a.x<b.x;
}
long long distance (point &A,point &B)
{
double dx=A.x-B.x;
double dy=A.y-B.y;
return dx*dx+dy*dy;
}
long long solve(vector<point>&a,long long l,long long r)
{
if(l==r)
{
return LONG_LONG_MAX;
}
if(r-l==1)
{
return distance(a[l],a[r]);
}
if(r-l==2)
{
return min(min(distance(a[l],a[l+1]),distance(a[l],a[r])),distance(a[l+1],a[r]));
}
long long mid=(l+r)/2;
long long ans1=solve(a,l,mid);
long long ans2=solve(a,mid+1,r);
long long delta=min(ans1,ans2);
long long ans3=delta;
vector<point>temp2;
for(long long i=l;i<=r;i++)
{
if(fabs(a[i].x-a[mid].x)<= sqrt(delta))
{
temp2.push_back(a[i]);
}
}
sort(temp2.begin(),temp2.end(),cmpy);
for(int i=0;i<temp2.size();i++)
{
for(int j=i+1;j<temp2.size();j++)
{
if(fabs((temp2[i].y-temp2[j].y))> sqrt(delta)||fabs((temp2[i].x-temp2[j].x))> sqrt(delta))
{
break;
}
else
{
ans3=min(ans3,distance(temp2[i],temp2[j]));
}
}
}
return(min(ans3,delta));
}
vector<point>a;
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
long long x;long long y;
scanf("%lld%lld",&x,&y);
a.push_back({x,y});
}
sort(a.begin(),a.end(),cmpx);
long long answer=solve(a,0,a.size()-1);
cout<<answer;
return 0;
}