Cod sursa(job #1267733)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 20 noiembrie 2014 10:35:53
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 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 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) )
 
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>, classcomp >::iterator itSt, itDr;
 
bool CMPX(pair<int, int> v1, pair<int, int> v2)
{
    return v1.first < v2.first;
}
 
 
int main()
{
    int i, st, dr, n, d;
    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);
     
    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]);
         
        d = int(dmin);
        /*
        itSt = lower_bound(S.begin(), S.end(),
                    make_pair(0, v[dr].second - d - 1));
        itDr = upper_bound(S.begin(), S.end(),
                    make_pair(0, v[dr].second + d));
         */
        /*
        fprintf(fout, "%d %d\n", itSt -> first, itSt -> second);
        fprintf(fout, "%d %d\n", itDr -> first, itDr -> second);
        fprintf(fout, "\n\n");
        */
        /*
        for(; itSt != itDr; ++itSt)
        {
            aux = sqrt( 1.0 * dist(*itSt, v[dr]) );
            if(aux < dmin) dmin = aux;
        }*/
        for(itSt = S.begin(); itSt != S.end(); ++itSt)
        {
            Ldist = dist(*itSt, v[dr]);
            aux = sqrt(1.0 * Ldist);
            
            if(aux < dmin) dmin = aux;
        }
        S.insert(v[dr]);
    }
     
    fprintf(fout, "%.6f\n", dmin);
    return 0;
}