147 pts求助!
查看原帖
147 pts求助!
908733
RidiculousBuffal_1楼主2023/1/27 22:59

用的是传统的分治的思想但是就是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;
}
2023/1/27 22:59
加载中...