Pagini recente » Cod sursa (job #2441190) | Cod sursa (job #1562865) | Cod sursa (job #15061) | Cod sursa (job #1210034) | Cod sursa (job #1472481)
#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#define MAX 100005
#define INF 4e18
#define x first
#define y second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n, i, j;
vector<pll> ordX, ordY, v(MAX);
ll dist(pll a, pll b){
return pow(a.x - b.x, 2) + pow(a.y - b.y, 2);
}
ll sol(int s, int d);
int main(){
f >> n;
ordX.resize(n), ordY.resize(n);
for(i = 0; i < n; i++)
f >> ordX[i].x >> ordX[i].y;
sort(ordX.begin(), ordX.end());
for(i = 0; i < n; i++)
ordY[i] = make_pair(ordX[i].y, ordX[i].x);
g << fixed << setprecision(6) << sqrt(sol(0, n));
return 0;
}
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 mins = sol(s, mij), mind = sol(mij, d);
ll min = mins < mind ? mins : mind;
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(i = s; i < d; i++)
if(abs(ordY[i].y - ordX[mij].x) < min)
v[size++] = ordY[i];
for(i = 0; i < size - 1; i++)
for(j = i + 1; j < size && j < i + 8; j++){
ll ds = dist(v[i], v[j]);
min = min < ds ? min : ds;
}
return min;
}