uva10245

"제목 대의: 가장 가까운 점의 거리를 찾아라. 10000보다 크면 인피니티와 같다.
사고방식: 처음에는 직접적으로 폭력적이라고 말하고 싶었지만 데이터를 보니 시간이 초과될 것 같아서 문제풀이를 보러 갔다.처음으로 분치 문제를 하다.
코드:

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

struct node {
    double x,y;
}n[10003];

bool cmp(node a, node b) {
    return a.x < b.x;
}

double dis(node a,node b) {
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double findmin(int a,int b) {
    if(a > b) return 40004;
    if(a == b-1) return dis(n[a],n[b]);
    int l = (a + b) / 2 , r = (a + b) / 2, mid = (a + b) / 2;
    double d = min(findmin(a,mid-1),findmin(mid+1,b));

    while(l >= a && d > n[mid].x - n[l].x) l--;
    while(r <= b && d > n[r].x - n[mid].x) r++;

    for(int i =  l + 1 ; i < r; i++) 
        for(int j = i + 1; j < r; j++)
            d = min(d,dis(n[i],n[j]));

    return d;
}

int main() {
    int N;
    while(scanf("%d",&N) && N) {
        for(int i = 0 ; i < N; i++) 
            scanf("%lf %lf",&n[i].x,&n[i].y);
        sort(n,n+N,cmp);
        double d =findmin(0,N-1);
        if(d >= 10000)
            printf("INFINITY
");
        else
            printf("%.4lf
",d);
    }

    return 0;
}