数据怎么回事?归并乱打过了?

P1429 平面最近点对(加强版)

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,改成正确的居然过不了!!!!大佬们为什么


|