Pagini recente » Cod sursa (job #1284270) | Cod sursa (job #1956831) | Cod sursa (job #1963278) | Cod sursa (job #917461) | Cod sursa (job #975833)
Cod sursa(job #975833)
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#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);
}
void merge(int st,int mid,int dr)
{
int i=st,j=mid+1;
vector<Pair> V;
while ( i <= mid && j <= dr )
{
if ( cmpy(B[i],B[j]) )
{
V.push_back( B[i++] );
continue;
}
if ( cmpy(B[j],B[i]) )
{
V.push_back( B[j++] );
continue;
}
V.push_back( B[i++] );
V.push_back( B[j++] );
}
while ( i <= mid ) V.push_back( B[i++] );
while ( j <= dr ) V.push_back( B[j++] );
for (unsigned int i=0,j=st;i<V.size();++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);
vector<Pair> V;
for (int i=st;i<=dr;++i)
if ( abs(B[i].x-A[mid].x) <= out )
V.push_back( B[i] );
int Size = V.size(), ct = 8;
for (int i=0;i<Size-1;++i)
for (int j=i+1;j<Size && 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";
}