Cod sursa(job #2134509)

Utilizator sandu.m.mdMorari Sandu sandu.m.md Data 18 februarie 2018 00:04:10
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct pair_double
{
    double x, y;
};

double dist(pair_double a, pair_double b){
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

bool cmp(pair_double a, pair_double b){
    bool ch = false;
    if(a.x < b.x)
        ch = true;
    else if(a.x == b.x && a.y < b.y)
        ch = true;
    return ch;
}

bool operator<(const pair_double& a, const pair_double& b)
{
    return a.y < b.y ? true : (a.y == b.y ? a.x < b.x : false);
}

vector<pair_double> vec, coada;
set<pair_double> by_y;
set<pair_double>::iterator down, up, it;
vector<pair_double>::iterator itc;
int n;
pair_double aux;
double minim = numeric_limits<double>::max();

int main(){

    fin >> n;
    for(int i = 0; i < n; i++){
        fin >> aux.x >> aux.y;
        vec.push_back(aux);
        by_y.insert(aux);
    }

    sort(vec.begin(), vec.end(), cmp);

    coada.push_back(vec[0]);

    double current;
    aux.x = 0;

    for(int i = 1; i < n; i++)
    {
        //cout << "1: " << vec[i].x << " " << vec[i].y << "\n";  
        for(itc = coada.begin(); itc != coada.end(); itc++)
        {
            aux = *itc;
            //cout << "2: " << aux.x << " " << aux.y << "\n";
            current = dist(vec[i], *itc);
            if(minim >= current)
            {
                minim = current;
            }
            else
            {
                coada.erase(itc);
            }
        }
        //cout << "2m: " << minim << "\n";         
        
        aux.y = vec[i].y - minim;
        aux.x = 0;
        //cout << "3: " << aux.y << " ";
        down = by_y.lower_bound(aux);
        aux.y = vec[i].y + minim;
        aux.x = numeric_limits<double>::max();
        //cout << aux.y << "\n";
        up = by_y.upper_bound(aux);
        for(it = down; it != up; it++)
        {
            aux = *it;
            if(aux.x != vec[i].x || aux.y != vec[i].y)
            {
                current = dist(vec[i], *it);
                if(minim > current)minim = current;
            }
        }
        //cout << "mi: " << minim << "\n";
        coada.push_back(vec[i]);
    }
    fout << setprecision(6);
    fout << fixed << minim << "\n";

    return 0;
}