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 谢谢谢谢