Cod sursa(job #2529403)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 23 ianuarie 2020 13:15:34
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.6 kb

#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#define ll long long
#define INF 100000000000000

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct {long long int x,y;};punct v[100005],posibil[100005];
int n;
bool cmp1(punct a,punct b)
{
    return a.x<b.x;
}
bool cmp2(punct a ,punct b)
{
    return a.y>b.y;
}
ll det_dist(punct a,punct b)
{
    ll sol=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    return sol;
}
ll solve(int st,int dr)
{
    if(dr-st<=3)
    {
        ll minim=INF;
        for(int i=st;i<dr;i++)
        {
            for(int j=i+1;j<=dr;j++)
            {
                ll p=det_dist(v[i],v[j]);
                if(p<minim) minim=p;
            }
        }
        return minim;
    }
    int mij=(st+dr)/2;
    ll stanga=solve(st,mij);
    ll dreapta=solve(mij+1,dr);
    ll distanta=min(stanga,dreapta);
    int cnt=0;
    for(int i=st;i<=dr;i++)
    {
        if(abs(v[i].x-v[mij].x)<=distanta)
        {
            posibil[++cnt]=v[i];
        }
    }
    sort(posibil+1,posibil+cnt+1,cmp2);
    ll dist_min=INF;
    for(int i=1;i<=cnt;i++)
    {
        for(int j=i+1;j<=min(cnt,i+9);j++)
        {
            ll p=det_dist(posibil[i],posibil[j]);
            if(dist_min>p)
            {
                dist_min=p;
            }

        }
    }
    if(dist_min<distanta) return dist_min;
    return distanta;

}
int main()
{

f>>n;
for(int i=1;i<=n;i++) f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp1);
ll rez=solve(1,n);
double rad=sqrt(rez);
g<<setprecision(6)<<fixed<<rad;




}