Cod sursa(job #1507574)

Utilizator sebinechitasebi nechita sebinechita Data 21 octombrie 2015 19:07:33
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <fstream>
#include <limits.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fi("cmap.in");
ofstream fo("cmap.out");
#define MAX 100100
#define INF 2000000000
struct Point{
	int x, y;
} p[MAX], y[MAX];
int n;
typedef long double ld;

ld dist(Point a, Point b)
{
	return sqrt(1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y));
}

inline bool cmp(Point a, Point b)
{
	return a.x < b.x;
}

ld closest(int st, int dr)
{
	if(st == dr)
		return INF;
	if(st == dr - 1)
		return dist(p[dr], p[st]);
	int mij = (st + dr) / 2;
	ld delta = min(closest(st, mij), closest(mij + 1, dr));
	ld x = p[mij].x + p[mij + 1].x;
	x /= 2;
	int i = st;
	int j = mij + 1;
	int f = 0;
	while(i <= mij && j <= dr)
	{
		if(p[i].x + delta < x)
			i++;
		else if(p[j].x - delta > x)
			j++;
		else
		{
			if(p[i].y < p[j].y)
			{
				y[++f] = p[i];
				i++;
			}
			else
			{
				y[++f] = p[j];
				j++;
			}
		}
	}
	while(i <= mij)
	{
		if(p[i].x + delta >= x)
			y[++f] = p[i];
		i++;
	}
	while(j <= dr)
	{
		if(p[j].x - delta <= x)
			y[++f] = p[j];
		j++;
	}
	for(i = 1 ; i <= f ; i++)
	{
		for(j = i + 1 ; j <= f ; j++)
		{
			if(y[j].y - delta > y[i].y)
				break;
			if(dist(y[i], y[j]) < delta)
				delta = dist(y[i], y[j]);
		}
	}
	return delta;
}
		

int main()
{
	fi >> n;
	for(int i = 1 ; i <= n ; i++)
	{ 
		fi >> p[i].x >> p[i].y;
	}
	sort(p + 1, p + n + 1, cmp);
	fo << fixed << setprecision(6) << closest(1, n) << "\n";
	
	fi.close();
	fo.close();
	return 0;
}