Pagini recente » Cod sursa (job #3261976) | Cod sursa (job #2958160) | Cod sursa (job #406854) | Cod sursa (job #2623687) | Cod sursa (job #2968722)
#include <bits/stdc++.h>
using namespace std;
#define int64 long long
#define MAX_N 100000
struct Point { int x, y; };
inline bool cmpByX(const Point& p1, const Point& p2) { return p1.x < p2.x; }
inline bool cmpByY(const Point& p1, const Point& p2) { return p1.y < p2.y; }
inline double dist(const Point& p1, const Point& p2) {
return sqrt(((int64)p1.x - p2.x) * (p1.x - p2.x) + ((int64)p1.y - p2.y) * (p1.y - p2.y));
}
int noPoints;
Point points[MAX_N];
int noMerged;
Point merged[MAX_N];
double bruteClosest(int left, int right) {
int i, j;
double minDist;
minDist = DBL_MAX;
for (i = left; i < right; ++i)
for (j = i + 1; j <= right; ++j)
minDist = min(minDist, dist(points[i], points[j]));
return minDist;
}
double mergeClosest(double minDist) {
int i, j;
sort(merged, merged + noMerged, cmpByY);
for (i = 0; i < noMerged - 1; ++i) {
j = i + 1;
while (j < noMerged && merged[j].y - merged[i].y < minDist) {
minDist = min(minDist, dist(merged[i], merged[j]));
++j;
}
}
return minDist;
}
double closest(int left, int right) {
if (right - left + 1 <= 3)
return bruteClosest(left, right);
int mid;
double minDist;
mid = (left + right) / 2;
minDist = min(closest(left, mid), closest(mid + 1, right));
noMerged = 0;
for (; left <= right; ++left)
if (abs(points[left].x - points[mid].x) < minDist)
merged[noMerged++] = points[left];
return min(minDist, mergeClosest(minDist));
}
int main() {
FILE *fin, *fout;
fin = fopen("cmap.in", "r");
fout = fopen("cmap.out", "w");
int i;
fscanf(fin, "%d", &noPoints);
for (i = 0; i < noPoints; ++i)
fscanf(fin, "%d%d", &points[i].x, &points[i].y);
sort(points, points + noPoints, cmpByX);
fprintf(fout, "%lf\n", closest(0, noPoints - 1));
fclose(fin);
fclose(fout);
return 0;
}