Cod sursa(job #2969244)

Utilizator GargantuanRoOprea Rares GargantuanRo Data 22 ianuarie 2023 19:13:10
Problema Cele mai apropiate puncte din plan Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
using namespace std;

ifstream cin ("cmap.in");
ofstream cout ("cmap.out");

const long long nmax = 2e5 + 7;

set<pair<long long,long long>>s,aux;

struct point
{
    long long x;
    long long y;
} p[nmax];

long long cmp(point a,point b) {
        return a.y < b.y;
}

long long dist_square(long long a,long long b,long long c,long long d) {
        return (a - b) * (a - b) + (c - d) * (c - d);
}

long long dmin;
int main()
{
    /*
    set<long long> ss = {1, 4, 7, 2, 5, 10};
    set<long long>::iterator it = ss.upper_bound(2);

    for (; it != ss.end(); ++it)
        cout << *it << ' ';
    */
        long long n,i;
        cin >> n;
        for(i=1; i<=n; i++)
        {
            cin >> p[i].x;
            cin >> p[i].y;
        }
        sort(p+1,p+n+1,cmp);
        dmin = dist_square(p[1].x,p[2].x,p[1].y,p[2].y);
        for(i=1; i<=n; i++)
        {
            long long xmin,xmax,ymin,ymax;
            xmin = p[i].x - dmin;
            xmax = p[i].x + dmin;
            ymin = p[i].y - dmin;
            ymax = p[i].y + dmin;
            auto it = s.lower_bound({xmin,0});
            auto it2 = s.upper_bound({xmax,0});
            for(; it != it2; it++)
                dmin = min(dmin, dist_square(p[i].x,it->first,p[i].y,it->second));
            s.insert({p[i].x,p[i].y});
        }
        double ans = sqrt(dmin);
        cout << std::fixed;
        cout  << setprecision(6) << ans;
        return 0;
}