Cod sursa(job #1046749)

Utilizator chimistuFMI Stirb Andrei chimistu Data 3 decembrie 2013 14:41:08
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#define maxn 100001
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define INF 1<<30

using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

struct punct{
    int 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 j,q,cont=1;
    double rez;
    punct Z[10000];
    if (st>=dr)
        return INFINITY;
    if(st+1 == dr)
        return dist(X[st],X[dr]);
    int mij = (st+dr)/2;
    rez = INFINITY;
    rez = min(rez,DivConq(st,mij));
    rez = min(rez,DivConq(mij+1,dr));
    //double rez = min(DivConq(st,mij),DivConq(mij+1,dr));
    for(int 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(int 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);
    g << setprecision(8) << DivConq(1,n);
    return 0;
}