Cod sursa(job #2138979)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 21 februarie 2018 23:41:37
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;



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

struct point
{
	int x, y;
};

point v[100001], v2[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 (upper - lower == 1)
	{
		return dist(v[lower], v[upper]);
	}

	if (upper - lower == 2)
	{
		long long res1 = dist(v[lower], v[lower+1]);
		long long res2 = dist(v[lower], v[lower+2]);
		if (res1 > res2)
			res1 = res2;
		res2 = dist(v[lower+1], v[lower+2]);
		if (res1 > res2)
			res1 = res2;

		return res1;
	}

	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 = mid; j = mid + 1;
	int l = v[mid].x + (v[mid+1].x - v[mid].x) / 2;
	while(i > 1 && v[i].x >= l - res1)
		i--;
	while(j < n && v[j].x <= l + res1)
		j++;
	for (int k = i; k <= j; k++)
	{
		v2[k] = v[k];
	}
	sort(v2 + i, v2 + j + 1, compare2);
	
	for (int k = i; k <= j; k++)
	{
		for (int l = 1; l <= 7; l++)
		{
			if (k + l <= j)
			{
				if (res1 > dist(v2[k], v2[k+l]))
					res1 = dist(v2[k], v2[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;
}