Cod sursa(job #1573588)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 19 ianuarie 2016 20:02:30
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#define MAXN 100100
#define inf 4e18

using namespace std;

struct coord
{
    int x, y;
    coord(int x = 0, int y = 0) : x(x), y(y) { }
};

int cmpAbscisa(coord a, coord b)
{
    if (a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}

double dist(coord a, coord b)
{
    double rez = sqrt(((double)a.x - b.x)*(a.x - b.x) + ((double)a.y - b.y) * (a.y - b.y));
	if (rez < 2)
		cerr <<"Baa";
	return rez;
}

int n;
coord v[MAXN], y[MAXN], aux[MAXN];

void citire()
{
	int x, yu;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &x, &yu);
        y[i] = v[i] = coord(x, yu);
	}
	sort (v+1, v+1+n, cmpAbscisa);
}

double solve(int st, int dr)
{
    if (dr - st <= 0)
		return inf;

    int mid = (st+dr)/2;

    double best = min(solve(st, mid), solve(mid+1, dr));
    /// left = [st, mid], right = [mid+1, dr]
    for (int i = st, j = mid+1, t1 = mid+1, t2 = dr+1, k = st; i < t1 || j < t2; k++) {
    	coord e;
        if (j >= t2 || i < t1 && y[i].y < y[j].y)
			e = y[i++];
		else
			e = y[j++];
		aux[k] = e;
    }
    for (int i = st; i <= dr; i++)
		y[i] = aux[i];
    for (int i = st, t = dr+1; i < t; i++)
		for (int j = i+1; j <= i+7 && j < t; j++)
			if (dist(y[i], y[j]) < best)
				best = dist(y[i], y[j]);
	return best;
}

int main()
{
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);

    citire();
    double rez = solve(1, n);
	printf("%.6lf", rez);

    return 0;
}