Cod sursa(job #1512089)

Utilizator DjokValeriu Motroi Djok Data 27 octombrie 2015 18:17:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<bits/stdc++.h>
using namespace std;

typedef struct lol {
    double x,y;
}troll;

struct CMP {
    bool operator () (const troll &a,const troll &b) const 
    {
      return a.y<b.y;
    }
};

int i,n,l,r;
double rs=1e18,best;
set <troll,CMP> s;
set <troll>::iterator it;
troll a[100005];

bool cmp(const troll &a,const troll &b) { return a.x<b.x; }

double dist(troll a,troll b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }

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

  ios_base::sync_with_stdio(0); cin.tie(0);

  cin>>n;
  for(i=1;i<=n;++i) cin>>a[i].x>>a[i].y;

  sort(a+1,a+n+1,cmp);

  for(l=r=1;r<=n;++r)
  {
    best=rs+1;

    while(l<r && a[l].x+best<a[r].x) s.erase(a[l++]);

    troll aux;
    aux.x=0; aux.y=a[r].y-best;

    for(it=s.lower_bound(aux);it!=s.end() && it->y<=a[r].y+best;++it) rs=min(rs,dist(*it,a[r]));

    s.insert(a[r]);
  }

  cout<<setprecision(10)<<fixed<<rs<<'\n';

 return 0;
}