Pagini recente » Cod sursa (job #1307976) | Cod sursa (job #2791353) | Cod sursa (job #814466) | Cod sursa (job #1937271) | Cod sursa (job #1472487)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define ll long long
#define MAX 100005
#define INF 4e18
#define x first
#define y second
#define pll pair<ll, ll>
using namespace std;
ifstream f("cmap.in") ;
ofstream g("cmap.out") ;
vector<pll> v(MAX), ordX, ordY;
ll dist(pll a, pll b){
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
ll sol(int s , int d){
if (s >= d - 1)
return INF;
if (d - s == 2){
if (ordY[s] > ordY[s + 1])
swap (ordY[s] , ordY[s + 1]);
return dist(ordX[s], ordX[s + 1]);
}
int mij = (s + d) / 2;
ll best = min(sol(s, mij), sol(mij , d));
merge(ordY.begin() + s, ordY.begin() + mij, ordY.begin() + mij, ordY.begin() + d, v.begin());
copy(v.begin(), v.begin() + (d - s), ordY.begin() + s);
int size = 0;
for (int i = s ; i < d ; i++)
if (abs(ordY[i].y - ordX[mij].x) <= best)
v[size ++] = ordY[i];
for (int i = 0; i < size - 1 ; ++ i)
for (int j = i + 1; j < size && j < i + 8 ; j++)
best = min(best, dist(v[i], v[j]));
return best ;
}
int main(){
int n;
f >> n ;
ordX.resize(n), ordY.resize(n);
for (int i = 0; i < (int) ordX.size(); i++)
f >> ordX [i].x >> ordX [i].y;
sort (ordX.begin(), ordX.end());
for (int i = 0; i < (int) ordX.size(); i++)
ordY[i] = make_pair(ordX[i].y, ordX[i].x);
g << fixed << setprecision(6) << sqrt (sol (0, n)) << "\n";
return 0;
}