Pagini recente » Cod sursa (job #479578) | Cod sursa (job #2818996) | Cod sursa (job #3233229) | Argumentatia | Cod sursa (job #2974622)
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
ifstream f ("cmap.in");
ofstream g ("cmap.out");
struct point {
int x , y;
};
vector < point > p;
int n;
bool cmp (point a , point b)
{
if (a.x < b.x)
return true;
if (a.x == b.x && a.y < b.y)
return true;
return false;
}
bool cmpaux (point a , point b)
{
if (a.y < b.y)
return true;
if (a.y == b.y && a.x < b.x)
return true;
return false;
}
double dist (point a , point b)
{
long long d1 = a.x - b.x;
long long d2 = a.y - b.y;
return sqrt (d1 * d1 + d2 * d2);
}
double distmin (vector < point > &p , int st , int dr)
{
if (dr - st <= 2)
{
double dmin = INT_MAX;
for (int i = st ; i < dr ; i++)
{
for (int j = i + 1 ; j <= dr ; j++)
dmin = min (dmin , dist (p[i] , p[j]));
}
return dmin;
}
int mij = (st + dr) / 2;
double dmin = min (distmin (p , st , mij) , distmin (p , mij + 1 , dr));
double d = (p[mij].x + p[mij + 1].x)/ 2.0;
vector < point > aux;
for (int i = st ; i <= dr ; i++)
if (abs (d - p[i].x) <= dmin)
aux.push_back (p[i]);
sort (aux.begin () , aux.end () , cmpaux);
int n = aux.size ();
for (int i = 0 ; i < n - 1 ; i++)
{
for (int j = i + 1 ; j < i + 8 && j < n ; j++)
dmin = min (dmin , dist (aux[i] , aux[j]));
}
return dmin;
}
int main()
{
f >> n;
p.resize (n);
for (int i = 0 ; i < n ; i++)
{
f >> p[i].x >> p[i].y;
}
sort (p.begin() , p.end() , cmp);
g << fixed << setprecision (6) << distmin (p , 0 , n - 1);
return 0;
}