Cod sursa(job #1573520)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 19 ianuarie 2016 19:21:14
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 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));
	return rez;
}

int n;
coord v[MAXN];

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

double solve(int st, int dr, vector<coord> &y)
{
    if (dr - st <= 0) {
		y.push_back(v[st]);
		return inf;
    }
//	else if (dr - st <= 1) {
//		if (v[st].y < v[dr].y)
//			y.push_back(v[st]), y.push_back(v[dr]);
//		else
//			y.push_back(v[dr]), y.push_back(v[st]);
//		return dist(v[st], v[dr]);
//	}
    int mid = (st+dr)/2;
    vector<coord> p1, p2;
    double best = min(solve(st, mid, p1), solve(mid+1, dr, p2));
    for (int i = 0, j = 0, t1 = p1.size(), t2 = p2.size(); i < t1 || j < t2; ) {
    	coord e;
        if (j >= t2 || i < t1 && p1[i].y < p2[j].y)
			e = p1[i++];
		else
			e = p2[j++];
		//if (abs(e.x - v[mid]) < best)
			y.push_back(e);
    }
    for (int i = 0, t = y.size(); i < t; i++)
		for (int j = i+1; j <= i+8 && 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);

	vector<coord> iy;
    citire();
    double rez = solve(1, n, iy);
	printf("%.6lf", rez);

    return 0;
}