特判求助
查看原帖
特判求助
324412
Filberte楼主2024/7/5 22:49

这份代码91分,加个“若有两点相同,输出0”的特判能过。

但我好奇我这个写法有什么问题吗?为啥两点相同的时候这份程序无法跑出正确的结果?

求大佬解释,谢谢

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
const double inf = 1e18;
int n;
struct Pt{
    double x, y;
}p[N];
double dis(int i, int j){return sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));}
double dis(Pt fi, Pt se){return sqrt((fi.x - se.x) * (fi.x - se.x) + (fi.y - se.y) * (fi.y - se.y));}
Pt lft[N], rit[N];
bool cmp1(Pt a, Pt b){return a.x != b.x ? a.x < b.x : a.y < b.y;}
bool cmp2(Pt a, Pt b){return a.y < b.y;}
double sol(int l, int r){
    int mid = (l + r) >> 1;
    if(l == r) return inf;
    if(l + 1 == r) return dis(l, r);
    double xmd = (p[mid].x + p[mid + 1].x) / 2.0;
    double cur = min(sol(l, mid), sol(mid + 1, r));
    int cl = 0, cr = 0;
    for(int i = l;i <= r;i++){
        if(p[i].x < xmd - cur || p[i].x > xmd + cur) continue;
        if(p[i].x <= xmd) lft[++cl] = p[i];
        else rit[++cr] = p[i];
    }
    if(!cl || !cr) return cur;
    sort(lft + 1, lft + 1 + cl, cmp2);
    sort(rit + 1, rit + 1 + cr, cmp2);
    int ptr = 1;double rs = inf;
    for(int i = 1;i <= cr;i++){
        while(rit[i].y - lft[ptr].y > cur && ptr < cl) ptr++;
        for(int j = ptr;j <= cl && abs(rit[i].y - lft[j].y) <= cur;j++) rs = min(rs, dis(rit[i], lft[j]));
    }
    return min(cur, rs);
}
int main(){
    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> p[i].x >> p[i].y;
    sort(p + 1, p + 1 + n, cmp1);
    cout << fixed << setprecision(4) << sol(1, n) << "\n";
    return 0;
}
2024/7/5 22:49
加载中...