Cod sursa(job #572340)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 5 aprilie 2011 11:16:30
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<stdio.h>
#include<math.h>
#include<set>
#include<algorithm>
using namespace std;
typedef pair<long long, long long> z;
int N;
z P[100000];
set<z> v1;
bool f1(z a, z b)
{return a.second<b.second;}
inline double dist(z a, z b)
{return	sqrt((a.second-b.second)*(a.second-b.second)+(a.first-b.first)*(a.first-b.first));}
double f2()
{if(N<=1)
  return -1;
sort(P,P+N,f1);
double ret = dist(P[0],P[1]);
v1.insert(P[0]);
for(int i=1,left=0;i<N;++i)
  {while(left<i && P[i].second-P[left].second>ret)
      v1.erase(P[left++]);
  for(set<z>::iterator it=v1.lower_bound(make_pair(P[i].first-ret,P[i].second-ret));it!=v1.end()&&P[i].first+ret>=(*it).first;++it)
     ret=min(ret,dist(P[i],*it));
  v1.insert(P[i]);}
return ret;}
int main()
{freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&N);
for(int i = 0;i<N;++i)
  scanf("%lld%lld",&P[i].second,&P[i].first);
double ret=f2();
printf("%lf\n",ret);
return 0;}