Cod sursa(job #1334626)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 4 februarie 2015 15:33:50
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define ll long long
#define inf 1LL<<63-3
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
 struct pct
 { int x,y; } p[100005],ps[100005],v[100005],m[100005];

bool comp1(pct a,pct b)
{ if (a.x<b.x) return 1;
  if (a.x>b.x) return 0;
   return a.y<b.y;
}

bool comp2(pct a,pct b)
{ if (a.y<b.y) return 1;
  if (a.y>b.y) return 0;
   return a.x<b.x;
}

ll Dist(pct i,pct j)
{ return 1LL*(i.x-j.x)*(i.x-j.x)+1LL*(i.y-j.y)*(i.y-j.y); }

int n,k,km;

void Merge(int st,int dr)
{ int i,mid=(st+dr)/2,i1,i2;

   km=0; i1=st; i2=mid+1;

  while(i1<=mid && i2<=dr)
  {
    if (comp2(ps[i1],ps[i2])) {km++; m[km]=ps[i1]; i1++;}
     else {km++; m[km]=ps[i2]; i2++;}
  }

  if (i1<=mid)
    for(;i1<=mid;i1++)
    {km++; m[km]=ps[i1];}

  if (i2<=dr)
    for(;i2<=dr;i2++)
    {km++; m[km]=ps[i2];}

  for(i=1;i<=km;i++)
   ps[i+st-1]=m[i];
}

ll Closest(int st,int dr)
{ ll res=inf,res1,res2; int i,j,mid=(st+dr)/2,ind=p[mid].x;

  if (dr-st+1<=3)
  {
    for(i=st;i<dr;i++)
     for(j=i+1;j<=dr;j++)
      {res1=(ll)Dist(p[i],p[j]);
       if (res1<res) res=res1;
      }
    sort(ps+st,ps+dr+1,comp2);

    return res;
  }
   res1=(ll)Closest(st,mid);
   res2=(ll)Closest(mid+1,dr);

 if (res1<res2) res=res1; else res=res2;
   Merge(st,dr);

   k=0;
  for(i=st;i<=dr;i++)
   if (ps[i].x>=ind-res && ps[i].x<=ind+res)
     {k++; v[k].x=ps[i].x; v[k].y=ps[i].y;}

   for(i=1;i<=k;i++)
    for(j=i+1;j<=i+7 && j<=k;j++)
     res=min(res,Dist(v[i],v[j]));


 return (ll)res;
}

int main()
{ int i,j; ll res=inf;
   f>>n;

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



    sort(p+1,p+n+1,comp1);

   for(i=1;i<=n;i++)
   { ps[i].x=p[i].x;
     ps[i].y=p[i].y;
   }

 g<<fixed<<setprecision(8)<<sqrt((ll)Closest(1,n))<<"\n";

  return 0;
}