Cod sursa(job #2139288)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 22 februarie 2018 13:01:00
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
#define ll long long
#define inf 9e18
using namespace std;



ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct point
{
	int x, y;
};

point v[100001], v2[100001], v3[100001];
int n;


bool compare(point a, point b)
{
	if (a.x < b.x)
		return true;
	if (a.x > b.x)
		return false;
	return true;
}

bool compare2(point a, point b)
{
	if (a.y < b.y)
		return true;
	if (a.y > b.y)
		return false;
	return true;
}

long long dist(point a, point b)
{
	return ((ll)a.x-(ll)b.x)*((ll)a.x-(ll)b.x)+((ll)a.y-(ll)b.y)*((ll)a.y-(ll)b.y);
}


long long solve(int lower, int upper)
{
	if (lower == upper)
		return inf;

	if (upper - lower == 1)
		return dist(v[lower], v[upper]);

	int mid = lower + (upper - lower) / 2, i, j;
	long long res1 = solve(lower, mid);
	long long res2 = solve(mid+1, upper);
	if (res1 > res2)
		res1 = res2;
	
	i = lower; j = mid + 1;
	double l = (double)v[mid].x + (v[mid+1].x - v[mid].x) / 2.0;
	
	for (int k = i; k <= j; k++)
		v2[k] = v[k];
	sort(v2 + i, v2 + j + 1, compare2);
	
	int c = 0;
	for (int k = i; k <= j; k++)
		if (fabs((double)v2[k].x - l) <= res1)
		{
			c++;
			v3[c] = v2[k];
		}
	for (int k = 1; k <= c; k++)
	{
		for (int l = 1; l <= 7; l++)
		{
			if (k + l <= c)
			{
				if (res1 > dist(v3[k], v3[k+l]))
					res1 = dist(v3[k], v3[k+l]);
			}
		}
	}

	return res1;
}

int main()
{
	int i;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> v[i].x >> v[i].y;
	fin.close();
	sort(v + 1, v + n + 1, compare);
	
	long long res = solve(1, n);
	fout << fixed << setprecision(6) << sqrt(res) << '\n';
	fout.close();
	return 0;
}