Fire_Raku @ 2023-08-20 08:48:14
一直找不出来错,其他的点 WA 了,我觉得可能就是小细节了,找不到QWQ
#include <bits/stdc++.h>
using namespace std;
long long read(){
long long x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c - '0');
c = getchar();
}
return x * f;
}
long long n;
int tmp[400010];
struct node{
long long x, y;
}a[400010], c[400010];
bool cmp1(node a, node b){
return a.x < b.x;
}
long long dist(int i, int j){
return (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
}
long long qsort(int l, int r){
long long d = 1ll << 62;
if(l == r) return d;
int mid = (l + r) >> 1, k = 0, lx = l, rx = mid + 1, tot = l;
long long lmin = qsort(l, mid), rmin = qsort(mid + 1, r);
d = min(lmin, rmin);
while(lx <= mid && rx <= r){
if(a[lx].y <= a[rx].y){
c[tot++] = a[lx++];
}
else c[tot++] = a[rx++];
}
while(lx <= mid) c[tot++] = a[lx++];
while(rx <= r) c[tot++] = a[rx++];
for(int i = l; i <= r; i++) a[i] = c[i];
long long dd = d;
dd = sqrt(d);
for(int i = l; i <= r; i++){
if(fabs(a[mid].x - a[i].x) <= dd){
tmp[++k] = i;
}
}
for(int i = 1; i <= k; i++){
for(int j = i + 1; j <= k && a[tmp[j]].y - a[tmp[i]].y <= dd; j++){
d = min(d, dist(tmp[i], tmp[j]));
dd = sqrt(d);
}
}
return d;
}
int main(){
n = read();
for(int i = 1; i <= n; i++){
a[i].x = read(), a[i].y = read();
}
sort(a + 1, a + n + 1, cmp1);
cout << qsort(1, n) << endl;
return 0;
}
by Fire_Raku @ 2023-08-20 09:13:44
找到了,a[mid].x 要在排序前保存下来
by Elma_ @ 2023-08-20 19:36:04
代码要自己调.jpg
by jr_linys @ 2023-09-20 11:35:03
@Fire_Raku 来自一个月后的感谢
by liuyinuo2 @ 2024-11-25 18:40:05
@Fire_Raku来自一年后的感谢