(UVA) 10245 - The Closest Pair Problem [最近點對]

https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1186

作法我是參考 演算法筆記 。

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 10006;
const double INF = 1e9 + 7;

struct P {
    double x,y;
    P() {}
    P(double _x,double _y) : x(_x),y(_y) {
        
    }
} p[MAX_N],tmp[MAX_N];

bool com_x(P p1,P p2) {
    return p1.x<p2.x || p1.x==p2.x && p1.y<p2.y;
}

bool com_y(P p1,P p2) {
    return p1.y<p2.y || p1.y==p2.y && p1.x<p2.x;
}

double dis(P p1,P p2) {
    return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}

double f(int L,int R) {
    if (L>=R) return INF;
    int mid=(L+R)>>1;
    double d=min(f(L,mid),f(mid+1,R));
    
    int sz=0;  //let's count how many number is near middle line
    for (int x=mid;   x>=L && p[mid].x - p[x].x < d ;x--) tmp[sz++]=p[x];
    for (int x=mid+1; R>=x && p[x].x - p[mid+1].x<d ;x++) tmp[sz++]=p[x];
    
    sort(tmp,tmp+sz,com_y);
    
    for (int i=0;sz>i;i++) {
        for (int j=1;3>=j && i+j<sz;j++) {
            d = min(d,dis(tmp[i],tmp[i+j]));
        }
    }
    
    return d;
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) return 0;
        for (int x=1;n>=x;x++) {
            double a,b;
            scanf("%lf %lf",&a,&b);
            p[x] = P(a,b);
        }
        sort(p+1,p+n+1,com_x);
        double ans=f(1,n);
        if (ans >= 10000) puts("INFINITY");
        else printf("%.4f\n",ans);
    }
}