Cod sursa(job #3167991)

Utilizator proflaurianPanaete Adrian proflaurian Data 11 noiembrie 2023 12:54:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.89 kb
#include <bits/stdc++.h>

#define punct pair<int,int>

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
punct v[100010];
set<punct>M;
int i,n,a,b,k;
double d,dist(punct,punct);
int main()
{
    /// se citesc punctele
    f>>n;
    for(i=0;i<n;i++)
    {
        f>>a>>b;
        v[i]=make_pair(a,b);
    }
    /// se sorteaza dupa x
    sort(v,v+n);
    /// se seteaza solutia "d" la "infinit"
    d=2000000001.0*sqrt(2.0);
    /// se adauga intr-un set de puncte, sotrat dupa y primul punct din stanga
    M.insert(make_pair(v[0].second,v[0].first));
    /// se parcurg punctele spre dreapta
    for(i=1;i<n;i++)
    {
        /// la fiecare punct

        /// elimin din set punctele situate "prea departe" pe orizontala fata de punctul curent
        /// mai precis se elimina orice punct care pe orizontala are distanta
        /// mai mare decat d fata de punctul curent !!!
        for(;(double)(v[i].first-v[k].first)>d;k++)
            M.erase(make_pair(v[k].second,v[k].first));
        /// acum in set au ramas puncte pe o banda vericala de latime  < d cu latura dreapta
        /// in punctul curent
        punct P=make_pair(v[i].second,v[i].first);
        /// iau punctul curent dar schimb X cu Y ( asa sunt puse punctele in set)
        /// is=iterator la primul punct din set care se afla la mai mult de
        /// Y_curent - d ( adica cu cel mult d mai jos)
        set<punct>::iterator
           is=M.lower_bound(make_pair((int)(P.first-d-1),-1000000001));
        /// acum parcurg elementele din set pana la cel mult Y_curent + d
        /// oricare astfel de punct are posibilitatea sa imbunatateasca solutia (sa micsoreze d)
        for(;is!=M.end()&&(double)(is->first-P.first)<=d;is++)
            d=min(d,dist(*is,P));
        /// dupa ce am procesat punctul curent il inserez si pe el in set
        M.insert(P);
    }
    g<<fixed<<setprecision(10)<<d;
    return 0;
}
double dist(punct A,punct B)
{
    double
    xa=(double)A.first,
    xb=(double)B.first,
    ya=(double)A.second,
    yb=(double)B.second;
    return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}
/// BOX care fata de punctul curent se extinde
    /// d spre stanga
    /// d in jos
    /// d in sus
/// daca e sa am o distanta mai buna cu punctul curent atunci ea e fata de un
/// punct situat pe acel BOX
/// se determina punctele din BOX ca o zona dintr-un set de puncte
/// sortat dupa Y si care contine doar puncte situate la cel mult distanta d
/// in stanga fata de X-ul punctului curent !!!



//  |           |
//  |           |
//  |           |
//  |-----------| y+d
//  |           |
//  |           |
//  |           |
//  |           |
//  |           |
// < -------- P(x,y)
//  |           |
//  |           |
//  |           |
//  |           |
//  |           |
//  |___________| y-d
//  |           |
//  |           |
//  |           |