Cod sursa(job #2527655)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 20 ianuarie 2020 19:09:28
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include <algorithm>

const int MAXN = 100000 + 5;

using namespace std;

typedef long long ll;

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


int n;
struct punct{
    ll x,y;
}v[MAXN],puncte_posibile[MAXN];

bool cmp_x(punct a,punct b){
    return a.x < b.x;
}
bool cmp_y(punct a,punct b){
    return a.y > b.y;
}
ll dist(punct a,punct b){
    return abs(a.x - b.x) * abs(a.x - b.x) + abs(a.y - b.y) * abs(a.y - b.y);
}

int divide(int l,int r){
    if(r - l <= 3){ /// ca sa evitam o submultime cu un singur punct
        ll minim = 2e18;
        for(int i = l; i <= r; i++){
            for(int j = l; j <= r; j++){
                if(j != i)
                    minim = min(minim,dist(v[i],v[j]));
            }
        }
        return minim;
    }
    int mij = (l + r) / 2; /// linia de mijloc intre puncte
    ll dreapta = divide(l,mij);
    ll stanga = divide(mij + 1,r);
    ll distanta = min(dreapta,stanga);

    int index = 0;
    for(int i = 1; i <= n; i++)
        if(abs(v[i].x - v[mij].x) <= dreapta)
            puncte_posibile[++index] = v[i];
    sort(puncte_posibile + 1,puncte_posibile + index + 1,cmp_y);
    ll distanta_minima = 2e18;
    for(int i = 1; i <= index; i++){
        for(int j = i + 1; j <= i + 8; j++){
            distanta_minima = min(distanta_minima,dist(puncte_posibile[i],puncte_posibile[j]));
        }
    }
    return min(distanta_minima,distanta);
}

int main()
{
    in>>n;
    for(int i = 1; i <= n; i++)
        in>>v[i].x>>v[i].y;
    sort(v + 1, v + n + 1,cmp_x);
    ll rezultat = divide(1,n);
//    ll distanta_minima = 2e18;
//    for(int i = 1; i <= n; i++){
//        for(int j = 1; j <= n; j++){
//            if(j != i)
//                distanta_minima = min(distanta_minima,dist(v[i],v[j]));
//        }
//    }
//    cout<<rezultat<<" "<<distanta_minima;
    out<<setprecision(10)<<fixed<<sqrt(rezultat);
    return 0;
}