Pagini recente » Cod sursa (job #1539039) | Cod sursa (job #191235) | Cod sursa (job #612733) | Istoria paginii runda/campion/clasament | Cod sursa (job #2067613)
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
long long const oo = 1LL*1<<60;
struct point
{
int x,y;
};
point P[100005], Aux[10005];
int n;
bool operator <(point A, point B)
{
if(A.x != B.x)
return A.x < B.x;
else
return A.y < B.y;
}
void Read() // citeste n puncte
{
int i, x, y;
f >> n;
point a; //citim cele n puncte
for(i = 0 ; i < n ; i++)
{
f >> x >> y;
a.x = x;
a.y = y;
P[i] = a;
}
sort(P , P + n); // sortam crescator cele n puncte dupa x, iar daca x-urile sunt egale,sortam crescator dupa y
}
long long dist(point A, point B) // distanta euclidiana calculata ca longlong,dar fara radical
{
return 1LL * (B.x - A.x) * (B.x - A.x) + 1LL * (B.y - A.y) * (B.y - A.y);
}
long long divide(int st,int dr)
{
if( st >= dr)
return oo;
if( dr - st <= 2)
{
long long mini = oo;
for(int i = st; i <= dr; ++i)
for(int j = i + 1; j <= dr; ++j)
mini = min(mini, dist(P[i], P[j]));
return mini;
}
int m = (st + dr) / 2,k=0;
long long a,b,c;
a = oo;
b = divide(st, m);
c = divide(m+1, dr);
a = min(b, c);
for(int i = m; i >= st && P[m].x - P[i].x <= a; i--)
Aux[k++] = P[i];
for(int i = m + 1; i <= dr && P[i].x - P[m].x <= a; i++)
Aux[k++] = P[i];
sort(Aux+1 , Aux + k);
for(int i = 0; i < k; ++i)
for(int j = i + 1; j < i + 8 && j < k; ++j)
a = min(a, dist(P[i], P[j]));
return a;
}
int main()
{
Read();
g<<fixed<<setprecision(6)<<sqrt(divide(0,n-1));
return 0;
}