Pagini recente » Borderou de evaluare (job #1799962) | Cod sursa (job #2412706) | Borderou de evaluare (job #1684414) | Borderou de evaluare (job #2017393) | Cod sursa (job #2412679)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("cmap.in"); ofstream fout ("cmap.out");
#define x first
#define y second
const int nmax = 1e5;
pair<int, int> v[nmax + 1], p[nmax + 1];
double dist (pair<int, int> a, pair<int, int> b) {
return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}
bool cmp (pair<int, int> a, pair<int, int> b) {
return a.y < b.y;
}
double solve (int st, int dr) {
if (dr - st + 1 <= 3) {
sort(v + st, v + dr + 1, cmp);
double ans = INFINITY;
for (int i = st; i <= dr; ++ i)
for (int j = i + 1; j <= dr; ++ j)
ans = min(ans, dist(v[i], v[j]));
return ans;
}
int mij = (st + dr) / 2;
double ans = min(solve(st, mij), solve(mij + 1, dr));
// interclasare dupa y
int ind = st;
int i = st, j = mij + 1;
while (i <= mij && j <= dr) {
if (v[i].y < v[j].y)
p[ind ++] = v[i ++];
else
p[ind ++] = v[j ++];
}
for (; i <= mij; ++ i) p[ind ++] = v[i];
for (; j <= dr; ++ j) p[ind ++] = v[j];
for (int i = st; i <= dr; ++ i)
v[i] = p[i];
// select punctele la dist ans de centru
ind = 0;
for (int i = st; i <= dr; ++ i)
if (fabs(v[i].x - v[mij].x) < ans)
p[ind ++] = v[i];
// urmatoarele 7 puncte
for (int i = 0; i < ind; ++ i)
for (int j = i + 1; j <= i + 7 && j < ind; ++ j)
ans = min(ans, dist(v[i], v[j]));
return ans;
}
int main () {
int n;
fin >> n;
for (int i = 1; i <= n; ++ i)
fin >> v[i].x >> v[i].y;
fout << setprecision(8) << fixed;
sort(v + 1, v + n + 1);
fout << solve(1, n) << "\n";
fin.close();
fout.close();
return 0;
}