Pagini recente » Cod sursa (job #1330348) | Autentificare | Istoria paginii runda/simulare-cartita-10 | Istoria paginii runda/simulare-cartita-15b/clasament | Cod sursa (job #1681544)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <limits.h>
#include <cmath>
#include <iomanip>
using namespace std;
struct pct {
long long x;
long long y;
};
ifstream in("cmap.in");
ofstream out("cmap.out");
long long dist;
pct v[100003];
pct v2[100003];
bool cmp(pct a, pct b) {
if(a.x != b.x)
return a.x < b.x;
else
return a.y < b.y;
}
bool cmp2(pct a, pct b) {
if(a.y != b.y)
return a.y < b.y;
else
return a.x < b.x;
}
inline long long distP(pct a, pct b) {
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long sm(int st, int dr) {
if(dr == st+1)
return distP(v[st], v[dr]);
int mid = (st+dr)/2;
long long minX = min(sm(st, mid), sm(mid, dr));
int line = (v[st].x+v[dr].x)/2;
int k = 0;
for(int i = st; i <= dr; i++)
if(abs(v[i].x-line) < minX)
v2[k++] = v[i];
sort(v2, v2+k, cmp2);
for(int i = 0; i < k; i++)
for(int j = i+1; j < k && j-i < 8; j++)
minX = min(minX, distP(v2[i], v2[j]));
return minX;
}
int main() {
int n;
in >> n;
for(int i = 1; i <= n; i++)
in >> v[i].x >> v[i].y;
sort(v, v+n, cmp);
out << fixed << setprecision(6) << sqrt(sm(1, n));
return 0;
}