Cod sursa(job #1026966)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 12 noiembrie 2013 12:27:24
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <fstream>
 
using namespace std;
 
struct punct { int x; int y;} v[100002];
 
void minim(double x, double y) 
{
    if (x - y > 0.000000001)
        x = y;
}
 
bool cmpx(punct a, punct b) 
{
    return a.x < b.x;
}
 
bool cmpy(punct a, punct b) 
{
    return a.y < b.y;
}
 
double dist(punct a, punct b) 
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
 
double dei(int st, int dr) {
    if (st >= dr)
        return 1 << 30;
 
    if (st + 1 == dr)
        return dist(v[st], v[dr]);
 
    int m = (st + dr) / 2;
 
    double min = 1 << 30;
 
    minim( min, dei(st, m));
    minim(min, dei(m + 1, dr));
 
    punct tmp[10100];
	
    int i, j, cnt = 0, contor;
 
    for (i = m; i >= st; i--)
        if (v[m].x - v[i].x <= min)
            tmp[++cnt] = v[i];
 
    for (i = m + 1; i <= dr; i++)
        if (v[i].x - v[m].x <= min)
            tmp[++cnt] = v[i];
 
    sort(tmp + 1, tmp + cnt + 1, cmpy);
 
    for (i = 1; i <= cnt; i++)
        for (j = i + 1, contor = 1; j <= cnt && contor <= 6; ++j, ++contor)
            minim(min, dist(tmp[i], tmp[j]));
 
    return min;
}
 
int main() {
 
    ifstream fin("cmap.in");
	ofstream fout("cmap.out");
 
    int n;
    fin >> n;
 
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x>>v[i].y;
 
    sort(v + 1, v + n + 1, cmpx);
 
    double dist = dei(1, n);
 
    fout<<dist;
 
    return 0;
}