Pagini recente » Cod sursa (job #2674680) | Cod sursa (job #1513570) | Cod sursa (job #426650) | Cod sursa (job #1559516) | Cod sursa (job #1984735)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int MAX = 100005;
struct Point{
int x, y;
bool operator < ( const Point& a ) const
{
return x < a.x;
}
};
using LL = long long;
vector<Point> a;
int N;
double dmin;
void Read();
LL Dist_Min( int st, int dr );
LL Dist( Point a, Point b );
LL Mod( LL x )
{
if ( x >= 0 )
return x;
return -x;
}
bool Comp( const Point& x, const Point& y )
{
return x.y < y.y || ( x.y == y.y && x.x < y.x );
}
int main()
{
Read();
LL r = Dist_Min(0, a.size() - 1);
dmin = sqrt(r);
fout << fixed << setprecision(6) << dmin << '\n';
fin.close();
fout.close();
return 0;
}
void Read()
{
fin >> N;
int x, y, i;
for ( i = 1; i <= N; ++i )
{
fin >> x >> y;
a.push_back({x, y});
}
sort( a.begin(), a.end() );
}
LL Dist_Min( int st, int dr )
{
if ( dr - st + 1 <= 3 )
{
if ( dr - st + 1 == 2 )
return Dist(a[st], a[dr]);
return min( min( Dist(a[st], a[st + 1]), Dist(a[st], a[st + 2]) ), Dist(a[st + 1], a[st + 2]) );
}
int mij = ( st + dr ) / 2;
LL s1 = Dist_Min(st, mij);
LL s2 = Dist_Min(mij + 1, dr);
LL sc = min(s1, s2);
vector<Point> P;
for ( int i = st; i <= dr; ++i )
if ( Mod(a[mij].x - a[i].x) <= sc )
P.push_back(a[i]);
sort(P.begin(), P.end(), Comp);
for ( size_t i = 0; i < P.size(); ++i )
for ( size_t j = i + 1; j < P.size() && j - i >= 7; ++j )
{
int dist = Dist(P[i], P[j]);
if ( dist < sc )
sc = dist;
}
return sc;
}
LL Dist( Point a, Point b )
{
return 1LL*( a.x - b.x )*( a.x - b.x ) + 1LL*( a.y - b.y )*( a.y - b.y );
}