Cod sursa(job #777261)

Utilizator danalex97Dan H Alexandru danalex97 Data 11 august 2012 18:08:53
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

#define ll long long

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

struct pct { int x, y, s;};

const int N = 100100;
const int DIST = 16;

int n;
ll rez = (ll)1<<62;
pct x[N];

inline bool cmp(const pct &a, const pct &b) {return a.s < b.s;}
inline ll min(const ll &a, const ll &b) {return a < b ? a : b;}
inline ll dist(const int &x1, const int &y1, const int &x2, const int &y2)
{	return (ll)(x2 - x1) * (x2 - x1) + (ll)(y2 - y1) * (y2 - y1); }

int main() 
{
	int i, j;
	
	in >> n;
	
	for(i = 1; i<=n; ++i)
		in >> x[i].x >> x[i].y, x[i].s = x[i].x + x[i].y;
	
	sort(x + 1, x + n + 1, cmp);
	
	for(i = 1; i!=n; ++i)
		for(j = i + 1; j <= i + DIST && j<=n; ++j)
			rez = min(rez, dist(x[i].x, x[i].y, x[j].x, x[j].y));
	
	out << setprecision(16) << sqrt((long double)rez) << "\n";
	
	return 0;
}