Cod sursa(job #2971898)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 28 ianuarie 2023 12:05:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100001
#define INF 1.7976931348623158e+308

struct pct {
    int x, y;
};
int n;
pct p[NMAX];
int nv;
pct pv[NMAX];

inline bool cmpx(const pct& p1, const pct& p2) {
    return p1.x==p2.x ? p1.y<p2.y : p1.x<p2.x;
}
inline bool cmpy(const pct& p1, const pct& p2) {
    return p1.y==p2.y ? p1.x<p2.x : p1.y<p2.y;
}

inline double dist(const pct& p1, const pct& p2) {
    return sqrt(((long long int)p1.x - p2.x) * (p1.x - p2.x) + ((long long int)p1.y - p2.y) * (p1.y - p2.y));
}

double finddistmin(int st, int dr) {
    double distmin;
    int i, j;

    distmin = INF;
    for (i=st; i<dr; i++) {
        for (j=i+1; j<=dr; j++) {
            distmin = min(distmin, dist(p[i], p[j]));
        }
    }
    
    return distmin;
}

double verif(double distmin) {
    int i, j;

    sort(pv, pv+nv, cmpy);

    for (i=0; i<nv-1; i++) {
        j = i+1;
        while (j<nv && pv[j].y-pv[i].y<distmin) {
            distmin = min(distmin, dist(pv[i], pv[j]));
            j++;
        }
    }
    
    return distmin;
}

double cmap(int st, int dr) {
    int mijl;
    double distmin;
    
    if (dr-st+1 <= 3) {
        return finddistmin(st, dr);
    }
    
    mijl = (dr+st)/2;
    distmin = min(cmap(st, mijl), cmap(mijl+1, dr));

    nv = 0;
    for (; st<=dr; st++) {
        if (abs(p[st].x-p[mijl].x) < distmin) {
            pv[nv] = p[st];
            nv++;
        }
    }

    return min(distmin, verif(distmin));
}

int main() {
    FILE *fin, *fout;
    fin = fopen("cmap.in", "r");
    fout = fopen("cmap.out", "w");
    
    int n, i;
    double rez;
    
    fscanf(fin, "%d", &n);
    
    for (i=0; i<n; i++) {
        fscanf(fin, "%d%d", &p[i].x, &p[i].y);
    }
    
    sort(p, p+n, cmpx);
    
    rez = cmap(0, n-1);
    fprintf(fout, "%lf\n", rez);
    
    fclose(fin);
    fclose(fout);
    return 0;
}