Cod sursa(job #2969145)

Utilizator Teodor94Teodor Plop Teodor94 Data 22 ianuarie 2023 17:01:53
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;

#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 ? p1.x < p2.x : p1.y < p2.y; }

inline double dist(const Point& p1, const Point& p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (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(points[i]);
        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;
}