wa了#2和#11,不知道为什么,已经调了一小时

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

Y_J_Y @ 2022-09-04 14:42:56

请求大佬帮助

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
    ll x=0,w=1;char ch=getchar();
    for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
    return x*w;
}
#define maxn 1000000
struct Point {
    double x,y;
}point[200005];
double dist(int a,int b) {
    return sqrt((point[a].x-point[b].x)*(point[a].x-point[b].x)+(point[a].y-point[b].y)*(point[a].y-point[b].y));
}
double solve(int l,int r) {
    if(l==r) return inf;
    if(l==r-1) return dist(l,r);
    int mid=(l+r)>>1;
    double min_d=min(solve(l,mid),solve(mid+1,r));
    for(int i=l;i<=mid;i++) {
        if(!(abs(point[mid].x-point[i].x)<min_d&&abs(point[mid].y-point[i].y)<min_d)) continue;
        for(int j=mid+1;j<=r;j++) {
            if(!(abs(point[mid].x-point[j].x)<min_d&&abs(point[mid].y-point[j].y)<min_d)) continue;
            min_d=min(min_d,dist(i,j));
        }
    }
    return min_d;
}
bool cmp(Point a,Point b) {
    return a.x<b.x; 
}
int main() {
    int n;n=read();
    for(int i=1;i<=n;i++) {
        scanf("%lf%lf",&point[i].x,&point[i].y);
    }
    sort(point+1,point+n+1,cmp);
    double ans =solve(1,n);
    printf("%.4lf",ans);
    return 0;
}

by Y_J_Y @ 2022-09-04 15:04:52

已过,原因是因为后面的y并没有排序,所以不能用mid的y来做标准


|