Cod sursa(job #779721)

Utilizator danielionutCojocaru ionut daniel danielionut Data 18 august 2012 17:01:04
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 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;
}