P1429 归并排序 wa了2和11

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

liyiHuan @ 2022-09-11 00:05:12

这题是不是不能用归并排序直接做出来?

#include <iostream>
#include <cmath>
#include <iomanip>
#include <asssert.h>
#define rep(i,a,b) for(int i=a;i<b;++i)
#define fr first
#define sc second

using namespace std;

const int N = 2e5 + 12, Inf = 0x3f3f3f;
typedef pair<int, int> pii;

int n;
double mx = Inf;
pii q[N], tmp[N];

inline double f(pii i, pii j)
{
    // 为什么这里直接相乘会变小 ? 
    double a = (i.fr-j.fr);
        a *= a;
    double b = (i.sc-j.sc);
        b *= b;
    return sqrt(a+b);
}

void megSort(int l, int r)
{
    if (l >= r) return ;

    int mid = l + r >> 1;

    megSort(l, mid), megSort(mid+1,r);

    int i=l, j=mid+1, k=0;

    while (i <= mid && j <= r)
    {   
        if (i <= mid && j <= r)
            mx = min(mx, f(q[i], q[j]));
        if (i <= mid && q[i] <= q[j])
            tmp[k ++ ] = q[i ++ ];
        else if (j <= r && q[i] >= q[j])
            tmp[k ++ ] = q[j ++ ];
    }

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++];

    for (int t=0;t < k;t ++ )
        q[l + t] = tmp[t];
}

int main()
{
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n;
    rep (i,0,n) cin >> q[i].fr >> q[i].sc;

//  rep (i,0,n) rep (j,0,n) if (i != j && fabs(f(q[i],q[j])-24603.7780) <= 0.02)
//      return cout<<i<<' '<<j, 0;

    megSort(0, n-1);

    cout << fixed << setprecision(4) << mx << endl;

    return 0;
}

/*
24603.7780

669 1728
*/

第二组数据 发现min是q[669]和q[1728]比较 感觉归并的时候没有枚举到这两个

所以感觉归并排序是不是错的,看了一眼题解,也没有用归并排序直接做出来的,怀疑是不是思路错了,有无dalao能帮我看看


by Register_int @ 2022-09-11 07:38:57

@liyiHuan 合理使用搜索


by liyiHuan @ 2022-09-11 13:22:38

@Register_int 谢谢谢谢


|