刚入门分治,求大佬教改代码

回复帖子

@伒銷朅潊 2020-09-16 18:18 回复
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
using namespace std;
struct node{
    double x;
    double y;
};
node a[200009];
int n;
double cmp(node x_,node y_)
{
    if(x_.x!=y_.x)
    {
        return x_.x<y_.x;
    }
    else return x_.y<y_.y;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    if(n==2)
    {
        double kkk=sqrt((a[1].x-a[2].x)*(a[1].x-a[2].x)+(a[1].y-a[2].y)*(a[1].y-a[2].y));
        printf("%.4lf",kkk);
        return 0;
    }
    sort(a+1,a+1+n,cmp);
    /*for(int i=1;i<=n;i++)
    {
        cout<<a[i].x<<" "<<a[i].y<<endl;
    }*/
    double l=a[1].x;
    double r=a[n].x;
    double mid=(l+r)/2;
    int bk;
    for(int i=1;i<=n;i++)
    {
        if(a[i].x>=mid)
        {
                bk=i-1;//这个地方本来是n-1,看着不对,就改过来了,交了一遍又多错了一个点
                break;
        } 
    }//1-bk为左边区间,bk+1为右边区间
    double min_front=0x7fffffff,min_last=0x7fffffff;
    for(int i=1;i<=bk;i++)
    {
        if(bk==1)
        {
            min_front=0;
            break;
        }
        for(int j=1;j<=bk;j++)
        {
            if(i!=j)
            {
                double kx=a[i].x-a[j].x;
                double ky=a[i].y-a[j].y;
                double gan=sqrt(kx*kx+ky*ky);
                min_front=min(min_front,gan);
            }
        }
    }//寻找两个区间的最小值 
    for(int i=bk+1;i<=n;i++)
    {
        if(bk+1==n)
        {
            min_last=0;
            break;
        }
        for(int j=bk+1;j<=n;j++)
        {
            if(i!=j)
            {
                double ox=a[i].x-a[j].x;
                double oy=a[i].y-a[j].y;
                double gand=sqrt(ox*ox+oy*oy);
                min_last=min(min_last,gand);
            }
        }
    }
    double ans;
    if(min_front==0)
    {
        ans=min_last;
    }
    else if(min_last==0)
    {
        ans=min_front;
    } 
    else ans=min(min_front,min_last);//如果为0则说明只有一个值;
    //则就给ans赋上另一个值 
    if(int(ans)==0)
    {
        ans=0x7fffffff;
    }
    int x_front=bk,x_last=bk+1;
    for(int i=bk;i>=1;i--)
    {
        if(mid-a[i].x>ans)
        {
            x_front=i+1;
            break;
        }   
    } 
    for(int i=bk+1;i<=n;i++)
    {
        if(a[i].x-mid>ans)
        {
            x_last=i-1;
            break;
        }
    }//找完两个独立的区间则再去找跨越两个区间的对点,并且他们到mid的横坐标差值应该
    //小于ans 
    double ans_cmp=0x7fffffff;
    for(int i=x_front;i<=bk;i++)
    {
        for(int j=x_last;i>=bk+1;i--)
        {
            double x_=a[i].x-a[j].x;
            double y_=a[i].y-a[j].y;
            double gandf=sqrt(x_*x_+y_*y_);
            ans_cmp=min(ans_cmp,gandf);
        } 
    }
    if(ans_cmp>ans)
    {
        printf("%.4f",ans);
    }
    else printf("%.4f",ans_cmp);
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。