Pagini recente » Cod sursa (job #897975) | Cod sursa (job #1595379) | Cod sursa (job #2498988) | Cod sursa (job #2574160) | Cod sursa (job #980873)
Cod sursa(job #980873)
#include<fstream>
#include<algorithm>
#include<vector>
#include<utility>
#define NMAX 100005
#include<cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
typedef pair < int , int > point ;
point v[NMAX] ;
int N;
const double oo ( 1<<30);
inline double dist ( point A , point B )
{
return sqrt ( ( long long )( A.first-B.first) * (A.first-B.first ) + (long long) ( A.second-B.second) *( A.second-B.second));
}
bool comp ( point A , point B )
{
return A.second < B.second;
}
double DEI (int st , int dr)
{
if (st >= dr)
return oo;
if (st == dr- 1)
{
if (v[st].second > v[dr].second)
swap(v[st],v[dr]);
return dist(v[st],v[dr]);
}
int m((st + dr) >> 1);
double x( min(DEI(st,m),DEI(m + 1,dr)) );
vector<point> pos;
int i;
for (i = st ; i <= dr ; ++i)
if (i != m)
if (abs(v[m].first - v[i].first) < x)
pos.push_back(v[i]);
int j, end;
sort(pos.begin(),pos.end(), comp);
for (i = 0 ; i < pos.size() ; ++i)
for (j = i + 1 ; j <= i + 8 && j < pos.size() ; ++j)
x = min(x,dist(pos[i],pos[j]));
return x;
}
int main ( void )
{
int i ;
double Answer = oo ;
f>>N;
for( i = 1 ; i <= N ; ++i )
f>>v[i].first>>v[i].second;
sort(v+1,v+N+1 ) ;
Answer = DEI(1,N);
g.precision(7);
g<<fixed<<Answer ;
}