Pagini recente » Cod sursa (job #1531601) | Cod sursa (job #3182579) | Cod sursa (job #113931) | Cod sursa (job #2233232) | Cod sursa (job #703928)
Cod sursa(job #703928)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n, ps;
double dmin;
pair<int, int> x[100001], y[100001], patrat[100001];
inline void citire()
{
freopen("cmap.in", "r", stdin);
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d %d", &x[i].first, &x[i].second);
}
inline void scriere()
{
freopen("cmap.out", "w", stdout);
printf("%.6f\n", dmin);
}
inline int sqdist(pair<int, int> a, pair<int, int> b)
{
return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
int dist(int s, int d)
{
if (d - s == 2)
{
if (y[s] > y[s + 1])
swap(y[s], y[s + 1]); //Sortam punctele dupa oY
return sqdist(x[s], x[s + 1]);
}
else if (s >= d - 1)
return 0x3f3f3f;
else
{
int m = (s + d) / 2; //Calculam jumatatea sirului
int temp_dist = min(dist(s, m), dist(m, d)); //Distanta minima din cele doua jumatati
sort(y + s, y + d); //Sortam punctele dupa oY
ps = 0;
for (int i = s; i < d; i++)
if (abs(y[i].second - x[m].first) <= temp_dist) //Punctul se afla la o distanta mai mica de temp_dist
{
patrat[ps] = y[i];
ps++;
}
for (int i = 0; i < ps - 1; i++)
for (int j = i + 1; j < ps; j++)
temp_dist = min(temp_dist, sqdist(patrat[i], patrat[j]));
return temp_dist;
}
}
inline void rezolvare()
{
sort(x, x + n);
for (int i = 0; i < n; i++)
y[i] = make_pair(x[i].second, x[i].first);
dmin = sqrt(dist(0, n));
}
int main()
{
citire();
rezolvare();
scriere();
return 0;
}