Cod sursa(job #1267745)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 20 noiembrie 2014 10:58:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
FILE *fout = fopen("cmap.out", "w");
#define Nmax 100000
#define ll long long
#define dist(a, b) ( 1LL * ((a).first - (b).first) * ((a).first - (b).first) + 1LL * ((a).second - (b).second) * ((a).second - (b).second) )


pair<int, int> v[Nmax];
 
bool CMPX(pair<int, int> v1, pair<int, int> v2)
{
    return v1.first < v2.first;
}
 
 
int main()
{
    int i, st, dr, n;
    ll Ldist;
    double dmin, aux;
    fin >> n;
    for(i = 0; i < n; ++i) fin >> v[i].first >> v[i].second;
     
    sort(v, v + n, CMPX);
    
    dmin = sqrt( 1.0 * dist(v[0], v[1]) );
     
    for(st = 0, dr = 2; dr < n; ++dr)
    {
        // la intrare in set este inclus intervalul [st, dr)
        for(; st < dr && 1.0 * (v[dr].first - v[st].first) >= dmin; ++st) ;
        
        for(i = st; i < dr; ++i)
        {
            Ldist = dist(v[i], v[dr]);
            aux = sqrt(1.0 * Ldist);
            
            if(aux < dmin) dmin = aux;
        }
    }
     
    fprintf(fout, "%.6f\n", dmin);
    return 0;
}