Pagini recente » Cod sursa (job #1193855) | Cod sursa (job #3147087) | Cod sursa (job #3252014) | Cod sursa (job #804011) | Cod sursa (job #3031834)
#include <bits/stdc++.h>
#include <fstream>
#define nmax 100005
#define x first
#define y second
#define epsilon 1e-4
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
pair <int, int> points[nmax];
int n;
long long mindist;
long long getPointsDist(pair<int, int> a, pair<int, int> b) {
return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}
bool cmp(pair<int, int> a, pair<int, int> b) {
if (a.y != b.y) {
return a.y > b.y;
}
return a.x < b.x;
}
long long getMinDist(int startPoint, int stopPoint) {
if (stopPoint == startPoint) {
return 8e18;
}
if (stopPoint == startPoint + 1) {
return getPointsDist(points[startPoint], points[stopPoint]);
}
int mid = (startPoint + stopPoint) >> 1;
long long crtMinDist = min( getMinDist(startPoint, mid), getMinDist(mid + 1, stopPoint));
long double actualMinDist = sqrt(crtMinDist * 1.0);
int d = points[mid].x;
vector <pair<int, int> > left, right;
for (int i = startPoint; i <= mid; i++) {
if (abs(points[i].x + actualMinDist -d) <= epsilon) {
left.push_back(points[i]);
}
}
for (int i = mid + 1; i <= stopPoint; i++) {
if (abs(points[i].x - actualMinDist - d) <= epsilon) {
right.push_back(points[i]);
}
}
sort(left.begin(), left.end(), cmp);
sort(right.begin(), right.end(), cmp);
int top = 0;
for (auto rightPoint : right) {
while(top < left.size()) {
if (abs(left[top].y - actualMinDist - rightPoint.y) <= epsilon) {
break;
} else {
top++;
}
}
if (top == left.size()) {
break;
}
for (int pos = top; pos < left.size(); pos++) {
if (abs(left[pos].y + actualMinDist - rightPoint.y) <= epsilon) {
break;
}
crtMinDist = min(crtMinDist, getPointsDist(left[pos], rightPoint));
}
}
return crtMinDist;
}
int main() {
fin>>n;
for (int i = 1; i <= n; i++) {
fin>>points[i].x>>points[i].y;
}
sort(points + 1, points + n + 1);
mindist = getMinDist(1,n);
fout<<setprecision(12)<<sqrt(mindist * 1.0);
}