Cod sursa(job #1268724)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 21 noiembrie 2014 12:46:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
#include <fstream>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
FILE *fout = fopen("cmap.out", "w");
#define Nmax 100000
#define oo 2100000000
#define ll long long
#define mp make_pair
#define dist(a, b) ( 1LL * ((a).first - (b).first) * ((a).first - (b).first) + 1LL * ((a).second - (b).second) * ((a).second - (b).second) )
  
struct classcomp
{
    bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) const
        {return lhs.second < rhs.second;}
};
  
bool operator< (const pair<int, int>& lhs, const pair<int, int>& rhs)
    {return lhs.second < rhs.second;}
  
pair<int, int> v[Nmax];
set< pair<int, int>, classcomp > S;
set< pair<int, int> >::iterator it, poz;
  
bool CMPX(pair<int, int> v1, pair<int, int> v2)
{
    return v1.first < v2.first;
}
  
  
int main()
{
    int i, st, dr, n, gata;
    double dmin, aux;
    fin >> n;
    for(i = 0; i < n; ++i) fin >> v[i].first >> v[i].second;
      
    sort(v, v + n, CMPX);
      
    S.insert(v[0]); S.insert(v[1]);
    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)
            S.erase(v[st]);
        
        S.insert(v[dr]);
        poz = S.find(v[dr]);
        
        if(poz != S.begin())
        {
            gata = 0;
            for(it = poz, --it; it != S.begin() && !gata; --it)
                if(v[dr].second - (it -> second) >= dmin) gata = 1;
                else
                {
                    aux = sqrt( 1.0 * dist(*it, v[dr]) );
                    if(aux < dmin) dmin = aux;
                }
            if(!gata)
            {
                aux = sqrt( 1.0 * dist(*it, v[dr]) );
                if(aux < dmin) dmin = aux;
            }
        }
        
        gata = 0;
        for(it = poz, ++it; it != S.end() && !gata; ++it)
            if((it -> second) - v[dr].second >= dmin) gata = 1;
            else
            {
                aux = sqrt( 1.0 * dist(*it, v[dr]) );
                if(aux < dmin) dmin = aux;
            }
    }
    
    fprintf(fout, "%.6f\n", dmin);
    return 0;
}