被卡了还是我写假了？

Micnation_AFO @ 2022-08-07 09:47:53

by Micnation_AFO @ 2022-08-07 09:48:34

稍微改一下就能 AC P1429：https://www.luogu.com.cn/record/82292147

by irris @ 2022-08-07 09:52:27

快来加入 multiset 邪教！！！1

by M1rac0 @ 2022-08-07 10:09:14

@Leap_hash_jperm 确实是写假了，用您的代码改了改，过了本题。

改得有点多，您自己对照着看一下吧：

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

const long long N = 4e5 + 10;
const long long INF = 1e18 + 10;

struct coord {
    long long x, y;
} a[N], tmp[N];

long long n;

bool cmp1(coord p, coord q) {
    return p.x < q.x;
}

bool cmp2(coord p, coord q) {
    return p.y < q.y;
}

long long dis(coord a, coord b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

long long merge(long long l, long long r) {
    if (l == r) return INF;
    long long mid = (l + r) >> 1, cnt = 0;
    long long v = merge(l, mid), w = merge(mid + 1, r);
    long long val = min(v, w);
    for (long long i = l; i <= r; i++)
        if ((a[i].x - a[mid].x) * (a[i].x - a[mid].x) <= val) tmp[++cnt] = a[i];
    sort(tmp + 1, tmp + 1 + cnt, cmp2);
    for (long long i = 1; i <= cnt; i++)
        for (long long j = i + 1; j <= cnt && (tmp[i].y - tmp[j].y) * (tmp[i].y - tmp[j].y) <= val; j++) 
            if (dis(tmp[i], tmp[j]) < val) val = dis(tmp[i], tmp[j]);
    return val;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].x, &a[i].y);
    sort(a + 1, a + 1 + n, cmp1);
    long long d = merge(1, n);
    printf("%lld\n", d);
    return 0;
}

by irris @ 2022-08-07 10:09:44

@Leap_hash_jperm if (abs(a[i].y - a[i].y) <= val) tmp[++cnt] = i;

by Micnation_AFO @ 2022-08-07 10:36:33

@AlgorithmerSnow @tratser

谢谢！确实写假太多地方了