Cod sursa(job #2969148)

Utilizator teochess2017Togan Teodor-Bogdan teochess2017 Data 22 ianuarie 2023 17:03:18
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <stdio.h>
#include <set>
#include <algorithm>

using namespace std;

#define MAXN 100000

///de pus long long!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

struct coord{
    double x, y;
    bool operator < (const coord &other) const{
        if(y < other.y){
            return true;
        }else{
            return false;
        }
    }
};
coord v[MAXN];
set <coord> ord;

void addpoint(coord pct, double &dmin){//trebuie sterse din set elementele care ies din rangeul de dmin pe axa Ox
    std::set<coord>::iterator lb, ub;
    double actd, actdmin;
    pct.y -= dmin;
    lb = ord.lower_bound(pct);
    pct.y += (2 * dmin);
    ub = ord.upper_bound(pct);
    actdmin = 0;
    while(lb != ub){
        actd = sqrt(((*lb).y - pct.y) * ((*lb).y - pct.y) + ((*lb).x - pct.x) * ((*lb).x - pct.x));
        if(actd < actdmin){
            actdmin = actd;
        }
        lb++;
    }
    if(actdmin < dmin){
        dmin = actdmin;
    }
}

int main()
{
    int n, i;
    double dmin;
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%lf%lf", &v[i].x, &v[i].y);
    }
    sort(v, v + n);
    ord.insert(v[0]);
    ord.insert(v[1]);
    dmin = sqrt((v[0].x - v[1].x) * (v[0].x - v[1].x) + (v[0].y - v[1].y) * (v[0].y - v[1].y));
    for(i = 2; i < n; i++){
        deletepoints();
        addpoint(v[2], dmin);
    }
    printf("%6lf", dmin);
    return 0;
}