Pagini recente » Cod sursa (job #2315146) | Cod sursa (job #2611895) | Cod sursa (job #725369) | Cod sursa (job #498285) | Cod sursa (job #975834)
Cod sursa(job #975834)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream F("cmap.in");
ofstream G("cmap.out");
#define x first
#define y second
typedef long long I64;
typedef pair<I64,I64> Pair;
const int Nmax = 100010;
const I64 oo = 1LL<<60;
Pair A[Nmax],B[Nmax];
int N;
bool cmpx( Pair a , Pair b )
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool cmpy( Pair a , Pair b )
{
return a.y == b.y ? a.x < b.x : a.y < b.y;
}
I64 sqr(I64 a)
{
return a*a;
}
I64 dist(Pair& a,Pair& b)
{
return sqr(a.x-b.x) + sqr(a.y-b.y);
}
Pair V[Nmax];
int Sz = 0;
void merge(int st,int mid,int dr)
{
int i=st,j=mid+1;
Sz = 0;
while ( i <= mid && j <= dr )
{
if ( cmpy(B[i],B[j]) )
{
V[++Sz] = B[i++];
continue;
}
if ( cmpy(B[j],B[i]) )
{
V[++Sz] = B[j++];
continue;
}
V[++Sz] = B[i++];
V[++Sz] = B[j++];
}
while ( i <= mid ) V[++Sz] = B[i++];
while ( j <= dr ) V[++Sz] = B[j++];
for (int i=1,j=st;i<=Sz;++i,++j) B[j] = V[i];
}
I64 go(int st,int dr)
{
if ( st >= dr )
return oo;
if ( dr - st == 1 )
{
if ( ! cmpy(B[st],B[dr]) )
swap( B[st],B[dr] );
return dist(A[st],A[dr]);
}
int mid = ( st + dr ) / 2;
I64 out = min( go(st,mid),go(mid+1,dr) );
merge(st,mid,dr);
Sz = 0;
for (int i=st;i<=dr;++i)
if ( abs(B[i].x-A[mid].x) <= out )
V[++Sz] = B[i];
int ct = 8;
for (int i=0;i<Sz-1;++i)
for (int j=i+1;j<Sz && j-i<ct;++j)
out = min( out,dist(V[i],V[j]) );
return out;
}
int main()
{
F>>N;
for (int i=1;i<=N;++i)
F>>A[i].x>>A[i].y;
sort(A+1,A+N+1,cmpx);
for (int i=1;i<=N;++i)
B[i] = A[i];
G<<fixed<<setprecision(6)<<sqrt(go(1,N))<<"\n";
}