Cod sursa(job #2924376)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 1 octombrie 2022 00:52:34
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

int n;
pair < int , int > v[100005],k[100005];

bool cmp(pair < int , int > a, pair < int , int > b) {
    return a.second>b.second;
}

void citire() {
    f >> n;
    for (int i=1;i<=n;i++) {
        f >> v[i].first >> v[i].second;
    }
    sort(v+1,v+n+1);
}

double dist(int p1, int p2) {
    int k1 = (v[p1].first-v[p2].first);
    int k2 = (v[p1].second-v[p2].second);
    return sqrt(k1*k1+k2*k2);
}

double dist2(int p1, int p2) {
    int k1 = (k[p1].first-k[p2].first);
    int k2 = (k[p1].second-k[p2].second);
    return sqrt(k1*k1+k2*k2);
}

double divide(int st, int dr) {
    if (st+1==dr) return dist(st,dr);
    if (st+2==dr) return min(dist(st,st+1),min(dist(st+1,dr),dist(st,dr)));
    int mij = (st+dr)/2;
    double dmin = min(divide(st,mij),divide(mij+1,dr));
    int ind = mij, aa = 0;
    while (ind && v[mij].first-v[ind].first<=dmin) {
        k[++aa]=v[ind];
        ind--;
    }
    ind = mij+1;
    while (ind<=n && v[ind].first-v[mij].first<=dmin) {
        k[++aa]=v[ind];
        ind++;
    }
    sort(k+1,k+aa+1,cmp);
    for (int i=1;i<=aa-7;i++) {
        for (int p=i+1;p<=i+7;p++) {
            dmin = min(dmin,dist2(i,p));
        }
    }
    return dmin;
}

int main()
{
    citire();
    g << fixed << setprecision(6) << divide(1,n);
    return 0;
}