Pagini recente » Cod sursa (job #2961138) | Cod sursa (job #2144558) | Cod sursa (job #1489672) | Cod sursa (job #2415175) | Cod sursa (job #2969159)
#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 ? p1.y < p2.y : p1.x < p2.x; }
inline bool cmpByY(const Point& p1, const Point& p2) { return p1.y == p2.y ? p1.x < p2.x : 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];
set<Point, decltype(cmpByY)*> activePoints(cmpByY);
int main() {
FILE *fin, *fout;
fin = fopen("cmap.in", "r");
fout = fopen("cmap.out", "w");
int i;
double minDist;
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);
minDist = DBL_MAX;
for (i = 0; i < noPoints; ++i) {
auto firstIt = activePoints.lower_bound({INT_MIN, points[i].y});
while (firstIt != activePoints.end() && firstIt->y - points[i].y <= minDist) {
if (points[i].x - firstIt->x > minDist)
firstIt = activePoints.erase(firstIt);
else
minDist = min(minDist, dist(*firstIt, points[i]));
++firstIt;
}
activePoints.insert(points[i]);
}
fprintf(fout, "%lf\n", minDist);
fclose(fin);
fclose(fout);
return 0;
}