Cod sursa(job #2139061)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 22 februarie 2018 01:04:00
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.1 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], 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 (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 = lower; j = mid + 1;
	long long l = v[mid].x;
	
	int aux_i = i, aux_j = mid+1, k = i;
	while(aux_i <= mid && aux_j <= j)
	{
		if (v[aux_i].y < v[aux_j].y)
		{
			v2[k] = v[aux_i];
			k++;
			aux_i++;
		}
		else if (v[aux_i].y > v[aux_j].y)
		{
			v2[k] = v[aux_j];
			k++;
			aux_j++;
		}
		else
		{
			v2[k] = v[aux_i];
			v2[k+1] = v[aux_j];
			aux_i++;
			aux_j++;
			k = k + 2;	
		}
	}

	while (aux_i <= mid)
	{
		v2[k] = v[aux_i];
		k++;
		aux_i++;
	}	

	while (aux_j <= j)
	{
		v2[k] = v[aux_j];
		k++;
		aux_j++;
	}
	
	int c = 0;
	for (int k = i; k <= j; k++)
		if (abs(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;
}