Cod sursa(job #3293218)

Utilizator ItsHezovPahonie George Alessio ItsHezov Data 10 aprilie 2025 19:57:02
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
typedef long long ll;
ll d;
struct P{ll x, y;}v[100001];
bool cmp(P a, P b)
{
    return a.x < b.x;
}
bool cmpY(P a, P b)
{
    return a.y < b.y;
}
ll sq(ll a){return a*a;}
ll dist(P a, P b)
{
    return (sq(a.x - b.x) + sq(a.y - b.y));
}
void solve(int st, int dr)
{
    if(st == dr) return;
    int mid = (st + dr) / 2;
    int middle_x = v[mid].x;
    solve(st,mid);
    solve(mid+1,dr);
    vector<P> stripe;
    for(int i = st;i<=dr;i++)
        if(sq(v[i].x - middle_x) <= d)
            stripe.push_back(v[i]);
    sort(stripe.begin(),stripe.end(),cmpY);
    for(int i = 0;i<stripe.size();i++)
        for(int j = i+1;j<stripe.size() && sq(stripe[i].y - stripe[j].y) < d;j++)
            d = min(d, dist(stripe[i],stripe[j]));
}

int main()
{
    int n;
    cin >> n ;
    for(int i = 1;i<=n;i++)
        cin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    d = 1e18;
    solve(1,n);
    long double ans = sqrtl(d);
    cout << fixed<<setprecision(6) << ans << '\n';
    return 0;
}