Cod sursa(job #2968721)

Utilizator Teodor94Teodor Plop Teodor94 Data 21 ianuarie 2023 20:41:20
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 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; }

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];

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;
}