Cod sursa(job #3155434)

Utilizator proflaurianPanaete Adrian proflaurian Data 8 octombrie 2023 12:28:50
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
const int N = 100010;
const int oo = 1000000010;
typedef pair<int,int> punct;

int n,m=1;
inline punct invers(punct A)
{
    swap(A.X,A.Y);
    return A;
}
punct P[N];
set<punct> Q;
double dist(punct A,punct B)
{
    return sqrt(1.0*(A.X-B.X)*(A.X-B.X)+1.0*(A.Y-B.Y)*(A.Y-B.Y));
}
double d;
int main()
{
    f>>n;
    for(int i=1; i<=n; i++)
    {
        int x,y;
        f>>x>>y;
        P[i]=make_pair(x,y);
    }
    sort(P+1,P+n+1);

    d=dist(P[1],P[2]);
    for(int i=1;i<=3;i++)Q.insert(make_pair(oo,oo));
    for(int i=1;i<=3;i++)Q.insert(make_pair(-oo,-oo));
    Q.insert(invers(P[1]));Q.insert(invers(P[2]));
    for(int i=3; i<=n; i++)
    {
        while(m<i&&  P[i].X-P[m].X >= d)
        {
            Q.erase(invers(P[m]));
            m++;
        }
        punct p=invers(P[i]);
        auto here=Q.lower_bound(p);
        auto sus=here;
        auto jos=here;
        while(sus->X-p.X<d)sus++;
        while(p.X-jos->X<d)jos--;jos++;
        for(auto it=jos;it!=sus;it++)
            d=min(d,dist(*it,p));
        Q.insert(p);
    }
    g<<fixed<<setprecision(10)<<d;
    return 0;
}