Cod sursa(job #2712410)

Utilizator stefantagaTaga Stefan stefantaga Data 25 februarie 2021 18:52:22
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define INF 1000000000
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
pair <int,int> a[100005];
set<pair<int,int>> v;
double distanta(pair <int, int > a,pair <int, int > b)
{
    return sqrt(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}
int i;
int limsus,limjos;
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1);
    double sol=2e9;
    int ind=1;
    for (i=1;i<=n;i++)
    {
        while (!v.empty()&&a[i].x-a[ind].x>=sol)
        {
            v.erase({a[ind].y,a[ind].y});
            ind++;
        }
        int limsus=a[i].y+(int)sol;
        int limjos=a[i].y-(int)sol;
        set <pair <int,int > > ::iterator jos=v.lower_bound({limjos,1e9});
        set <pair <int,int>  > ::iterator sus=v.lower_bound({limsus,1e9});
        for (set <pair<int,int> > ::iterator  j=jos;j!=sus;j++)
        {
            pair <int,int>  nr=*j;
            swap(nr.x,nr.y);
            double dist=distanta(nr,a[i]);
            sol=min(sol,dist);
        }
        v.insert({a[i].y,a[i].x});
    }
    g<<setprecision(6)<<fixed;
    g<<sol<<'\n';
    return 0;
}