Cod sursa(job #1611070)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 23 februarie 2016 22:20:58
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;
const int eps = 0.0000001;

typedef long long Tpoint;

int n;

class Point {

public:
	Tpoint x; Tpoint y;

	Point() : x(0), y(0) { }

	Point(Tpoint x, Tpoint y) : x(x) , y(y) { }

};

vector<Point> v;

void read() {

	fin >> n ; 

	for(int i = 1; i <= n; ++i) {

		Tpoint x; Tpoint y;

		fin >> x >> y;

		v.push_back({x, y});
	}
}

bool compareX(const Point& a, const Point& b) {
	return a.x < b.x;
}

bool compareY(const Point& a, const Point& b) {
	return a.y < b.y;
}


double distance(const Point& a, const Point& b) {

	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) ;
}

Tpoint mod(Tpoint x) { return x < 0 ? -x : x; }

int lowerBoundX(Tpoint value, vector<Point>& v) {

	int pos = 0 ; int step = 1;

	for(; step <= n - 1; step <<= 1);

	for( ; step ; step /= 2)
		if(pos + step <= n - 1 && v[pos + step].x < value)
			pos += step;
	
	if(pos < n - 1)
		return pos + 1;

	return pos;
}

int upperBoundX(Tpoint value, vector<Point>& v) {

	int pos = 0 ; int step = 1;

	for(; step <= n - 1; step <<= 1);

	for( ; step ; step /= 2)
		if(pos + step <= n - 1 && v[pos + step].x <= value)
			pos += step;

	return pos;
}

double findDistance(int st, int dr, vector<Point>& v) {

//la 3 puncte ne oprim
	if(dr - st <= 2 )  {
		//sunt minim 2
		double min1 = distance(v[st], v[st + 1]);

		if(st + 2 < n)
			return min(min1, distance(v[st + 1], v[st + 2]) );
		return min1;
	}

	int median = st + (dr - st) / 2;
	double minD = min(findDistance(st, median, v), findDistance(median + 1, dr, v));

	//int leftIndex = lowerBoundX(v[median].x - minD , v);
	//int rightIndex = upperBoundX(v[median].x + minD, v);

	vector<Point> m;

	for(int i = st; i <= dr; ++i)
		if( (v[i].x - v[median].x) * (v[i].x - v[median].x) <= minD )
			m.push_back(v[i]);

	sort(m.begin(), m.end(), compareY);

	for(unsigned i = 0 ; i < m.size(); ++i)
		for(unsigned j = i + 1; j <= i + 7 && j < m.size(); j++)
			minD = min(minD, distance(m[i], m[j]));

	return minD;
}

void solve() {

	sort(v.begin(), v.end(), compareX);
 
	fout << fixed << setprecision(6) <<  sqrt(findDistance(0, n - 1, v));
}

int main() {

	read();

	solve();

	return 0;

}