Cod sursa(job #1071615)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 3 ianuarie 2014 11:11:58
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#define maxn 100001
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define INF 3000000000
#include <stdio.h>
 
using namespace std;
 
ifstream f("cmap.in");
ofstream g("cmap.out");
 
struct punct{
    long long x,y;
};
 
punct X[maxn];
int n;
 
bool dupax(punct Q, punct R){
    return Q.x < R.x;
}
 
bool dupay(punct Q, punct R){
    return Q.y < R.y;
}
 
double dist(const punct &A, const punct &B){
    return sqrt((A.x - B.x)*(A.x - B.x)+(A.y-B.y)*(A.y-B.y));
}
 
double DivConq(int st, int dr){
    int i,j,q,cont=0;
    double rez;
    punct Z[10200];
    if (st>=dr)
        return INF;
    if(st+1 == dr)
        return dist(X[st],X[dr]);
    int mij = (st+dr)/2;
    rez = INF;
    rez = min(rez,DivConq(st,mij));
    rez = min(rez,DivConq(mij+1,dr));
    for(i=st;i<=dr;++i)
        if(abs(X[mij].x - X[i].x) <= rez)
            Z[++cont] = X[i];
    sort(Z+1, Z+1+cont,dupay);
    for(i=1;i<cont;++i){
        for(j = i + 1; (j <= cont) && ((j-i) < 5); ++j, ++q){
            rez = min(rez,dist(Z[i],Z[j]));
            }
    }
    return rez;
}
 
int main()
{
    f >> n;
    for(int i=1;i<=n;i++){
        f >> X[i].x >> X[i].y;
    }
    sort(X+1,X+n+1,dupax);
    freopen("cmap.out", "w", stdout);
    printf("%.6lf\n",DivConq(1,n));
    return 0;
}