Cod sursa(job #2582756)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 17 martie 2020 12:44:35
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>

#define MAX 100010

#define x first
#define y second

using namespace std;
typedef long double db;
typedef long long ll;

ll n,sz;
pair<ll,ll> a[MAX],vp[MAX];

db dis(pair<ll,ll> p1, pair<ll,ll> p2){
  return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

bool cmp(pair<ll,ll> p1, pair<ll,ll> p2){
  return p1.y<p2.y;
}

db rez(ll st,ll dr){
  if(dr-st+1<=3){
    db ansa;
    ansa=dis(a[st],a[st+1]);
    if(dr-st+1==3)
      ansa=min(ansa,min(dis(a[st],a[dr]),dis(a[dr],a[dr-1])));
    return ansa;
  } else {
    ll mij=(st+dr)/2;
    db ans1=rez(st,mij);
    db ans2=rez(mij+1,dr);
    db ansa=min(ans1,ans2);
    ll drd=a[mij].x;
    sz=0;
    for(ll i=mij;a[i].x>=drd-ansa&&i>=0;i--) vp[++sz]=a[i];
    for(ll i=mij+1;a[i].x<=drd+ansa&&i<=n;i++) vp[++sz]=a[i];
    sort(vp+1,vp+sz+1,cmp);
    for(ll i=1;i<=sz;i++)
      for(ll j=i+1;j<=i+7&&j<=sz;j++)
        ansa=min(ansa,dis(vp[i],vp[j]));
    return ansa;
  }
}

int main()
{
    ifstream f ("cmap.in");
    ofstream g ("cmap.out");
    f>>n;
    for(ll i=1;i<=n;i++)
      f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    g<<fixed<<setprecision(6)<<rez(1,n)<<'\n';
    f.close ();
    g.close ();
    return 0;
}