Cod sursa(job #1282517)

Utilizator fhandreiAndrei Hareza fhandrei Data 4 decembrie 2014 12:54:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.35 kb
// FMI - Grupa 135 - Semigrupa 2 - Hareza Andrei
// Include
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;

// Definitii
#define ll long long

// Clase
class point_t
{
	int x, y;
public:
	point_t()
	{
		x = y = 0;
	}
	
	bool operator<(point_t p) const
	{
		return x == p.x? y < p.y : x < p.x;
	}
	bool operator<<(point_t p) const
	{
		return y == p.y? x < p.x : y < p.y;
	}
	
	ll distTo(point_t p)
	{
		return 1LL*(x-p.x) * (x-p.x) + 1LL*(y-p.y) * (y-p.y);
	}
	int xDist(point_t p)
	{
		int dist = x -p.x;
		return dist<0? -dist : dist;
	}
	
	friend istream &operator>>(istream &file, point_t &p);
};
istream &operator>>(istream &file, point_t &p)
{
	file >> p.x >> p.y;
	return file;
}

// Constante
const int sz = 100001;
const ll oo = (1LL<<63)-1LL;

// Functii
ll findDist(int left, int right);

// Variabile
ifstream in("cmap.in");
ofstream out("cmap.out");

int num;

point_t points[sz], temp[sz];

// Main
int main()
{
	in >> num;
	for(int i=1 ; i<=num ; ++i)
		in >> points[i];
	
	sort(points+1, points+num+1);
	
	out << fixed << setprecision(6) << sqrt(findDist(1, num));
	
	in.close();
	out.close();
	return 0;
}

ll findDist(int left, int right)
{
	if(right - left < 2)
	{
		if(right == left)
			return oo;
		else
		{
			if(points[right] << points[left])
				swap(points[left], points[right]);
			return points[left].distTo(points[right]);
		}
	}
	
	int mid = (left + right) / 2;
	point_t midPoint = points[mid];
	ll dist = min(findDist(left, mid), findDist(mid+1, right));
	
	int left1 = left, right1 = mid;
	int left2 = mid+1, right2 = right;
	
	int current = left-1;
	while(left1 <= right1 && left2 <= right2)
	{
		if(points[left1] << points[left2])
			temp[++current] = points[left1++];
		else
			temp[++current] = points[left2++];
	}
	
	while(left1 <= right1)
		temp[++current] = points[left1++];
	
	while(left2 <= right2)
		temp[++current] = points[left2++];
	
	for(int i=left ; i<=right ; ++i)
		points[i] = temp[i];
	
	int tempSize = 0;
	for(int i=left ; i<=right ; ++i)
		if(midPoint.xDist(points[i]) < dist)
			temp[++tempSize] = points[i];
	
	for(int i=1 ; i<=tempSize ; ++i)
		for(int j=i+1 ; j<=tempSize && temp[i].distTo(temp[j]) < dist; ++j)
			dist = temp[i].distTo(temp[j]);
	
	return dist;
}