Cod sursa(job #703928)

Utilizator blustudioPaul Herman blustudio Data 2 martie 2012 15:28:54
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n, ps;
double dmin;
pair<int, int> x[100001], y[100001], patrat[100001];

inline void citire()
{
	freopen("cmap.in", "r", stdin);
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d %d", &x[i].first, &x[i].second);
}
inline void scriere()
{
	freopen("cmap.out", "w", stdout);
	printf("%.6f\n", dmin);
}
inline int sqdist(pair<int, int> a, pair<int, int> b)
{
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
int dist(int s, int d)
{
	if (d - s == 2)
	{
		if (y[s] > y[s + 1])
			swap(y[s], y[s + 1]); //Sortam punctele dupa oY
		return sqdist(x[s], x[s + 1]);
	}
	else if (s >= d - 1)
		return 0x3f3f3f;
	else
	{
		int m = (s + d) / 2; //Calculam jumatatea sirului
		int temp_dist = min(dist(s, m), dist(m, d)); //Distanta minima din cele doua jumatati
		sort(y + s, y + d); //Sortam punctele dupa oY
		ps = 0;
		for (int i = s; i < d; i++)
			if (abs(y[i].second - x[m].first) <= temp_dist)	//Punctul se afla la o distanta mai mica de temp_dist
			{
				patrat[ps] = y[i];
				ps++;
			}
		for (int i = 0; i < ps - 1; i++)
			for (int j = i + 1; j < ps; j++)
				temp_dist = min(temp_dist, sqdist(patrat[i], patrat[j]));
		return temp_dist;
	}
}
inline void rezolvare()
{
	sort(x, x + n);
	for (int i = 0; i < n; i++)
		y[i] = make_pair(x[i].second, x[i].first);
	dmin = sqrt(dist(0, n));
}
int main()
{
	citire();
	rezolvare();
	scriere();
	return 0;
}