Cod sursa(job #3293467)

Utilizator Tudor_CCTudor Cocu Tudor_CC Data 11 aprilie 2025 19:09:25
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

struct el
{
    double long x,y;
};
el v[100005];

double long  t;

bool ord1(const el & a,const el & b)
{
    if(a.x<b.x)
    {
        return true;
    }
    return false;
}

bool ord2(const el & a,const el & b)
{
    if(a.y<b.y)
    {
        return true;
    }
    return false;
}

void rez(int a,int b)
{
    if(a==b)
    {
        return;
    }
    int mij=(a+b)/2;
    rez(a,mij);
    rez(mij+1,b);
    vector <el> s;
    for(int i=a;i<=b;++i)
    {
        if((v[i].x-v[mij].x)*(v[i].x-v[mij].x)<=t)
        {
            s.push_back(v[i]);
        }
    }
    sort(s.begin(),s.end(),ord2);
    for(int i=0;i<s.size()-1;++i)
    {
        for(int j=i+1;j<s.size();++j)
        {
            if(((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y))>t)
            {
                break;
            }
            else
            {
                if(((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y))<t)
                {


                t=((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y));
                }
            }
        }
    }
}

int main()
{
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,ord1);
    t=1e18;
    rez(1,n);
    t=sqrt(t);
    cout<<fixed<<setprecision(6)<<t;
    return 0;
}