Pagini recente » Monitorul de evaluare | Cod sursa (job #2471981) | Cod sursa (job #2467864) | Cod sursa (job #2572852) | Cod sursa (job #2472130)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point{
long long x, y;
};
int n;
point v[10005];
void citire() {
fin >> n;
for (int i = 0; i < n; ++i) {
fin >> v[i].x >> v[i].y;
}
}
bool comp(point p1, point p2) {
return p1.x < p2.x;
}
long double dBetween2(point p1, point p2) {
long long x = p1.x - p2.x;
long long y = p1.y - p2.y;
return sqrt(x * x + y * y);
}
void intercl(int st, int mij, int dr) {
int i = st, j = mij;
vector<point> aux;
while (i < mij && j <= dr) {
if (v[i].y < v[j].y) {
aux.push_back(v[i]);
++i;
}
else {
aux.push_back(v[j]);
++j;
}
}
while (i < mij) {
aux.push_back(v[i++]);
}
while (j <= dr) {
aux.push_back(v[j++]);
}
for (unsigned l = 0; l < aux.size(); ++l) {
v[l + st] = aux[l];
}
}
long double det(int st, int dr) {
long double ans = 99999999999999999;
if (st >= dr)
return ans;
if (dr - st == 1) {
if (v[st].y > v[dr].y) {
swap(v[st], v[dr]);
}
return dBetween2(v[st], v[dr]);
}
int mij = (st + dr) / 2;
ans = min(det(st, mij), det(mij + 1, dr));
intercl(st, mij, dr);
for (int i = st; i <= dr; ++i) {
for (int j = i + 1; j <= dr && j - i <= 6; ++j) {
ans = min(dBetween2(v[i], v[j]), ans);
}
};
return ans;
}
int main()
{
citire();
sort(v, v + n, comp);
fout << fixed << setprecision(6) << det(0, n - 1) << "\n";
return 0;
}