Cod sursa(job #1718261)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 17 iunie 2016 10:01:29
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
ifstream fin("cmap.in");
FILE *fout = fopen("cmap.out", "w");
using ll = long long;
using pii = pair<int,int>;
#define Nmax 100000
#define INF 1100000000
#define mp make_pair

struct CMPY
{
	bool operator() (const pii& p1, const pii& p2) const
	{
		return p1.second < p2.second;
	}
};

pair<int, int> v[Nmax];
set< pair<int, int>, CMPY > S;
set< pair<int, int> >::iterator itBegin, itEnd;

bool CMPX(const pii& p1, const pii& p2)
{
	return p1.first < p2.first;
}

double dist(const pii &p1, const pii &p2)
{
	double d = 1.0 * (p1.first - p2.first) * (p1.first - p2.first) + 1.0 * (p1.second - p2.second) * (p1.second - p2.second);
	return sqrt(d);
}


int main()
{
	int i, st, dr, n;
	double dmin;

	fin >> n;
	for (i = 0; i < n; ++i) fin >> v[i].first >> v[i].second;

	sort(v, v + n, CMPX);

	dmin = INF;
	for (st = dr = 0; dr < n; ++dr)
	{
		// la intrare in set este inclus intervalul [st, dr)
		for (; st < dr && 1.0 * (v[dr].first - v[st].first) >= dmin; ++st)
			S.erase(v[st]);

		itBegin = S.lower_bound(mp(0, v[dr].second - dmin));
		itEnd = S.upper_bound(mp(0, v[dr].second + dmin));

		for (auto it = itBegin; it != itEnd; ++it)
		{
			dmin = min(dmin, dist(v[dr], *it));
		}

		S.insert(v[dr]);
	}

	fprintf(fout, "%.6f\n", dmin);
	return 0;
}