#include <stdio.h>
#include <float.h>
#include <math.h>

#define maxp 100
#define maxfol 5

typedef struct
 {
 float x,y;
 int id;
 } bod;

#define sqr(X) ((X)*(X))
#define dist2(X,Y) (sqr((X).x-(Y).x)+sqr((X).y-(Y).y))	/* Vzdálenost bodů */

bod temp[maxp+1],body[maxp];	/* ; Načtené body */

/* Pomocná makra, abychom mohli třídit podle X nebo Y */
#define dMerge(x)\
void Merge##x(bod co[],int od,int s,int k)\
 {\
 int i1=od,i2=s,kam=od;\
 while (kam<k)\
  {\
  while (i1<s&&(i2==k||co[i1].x<co[i2].x)) temp[kam++]=co[i1++];\
  while (i2<k&&(i1==s||co[i1].x>=co[i2].x)) temp[kam++]=co[i2++];\
  }\
 for (i1=od;i1<k;i1++) co[i1]=temp[i1];\
 }

dMerge(x)
dMerge(y)

/* Třídění MergeSortem */
void MergeSort(bod co[],int od,int k)
 {
 if (od+1<k)
  {
  int div=(od+k)/2;
  MergeSort(co,od,div);
  MergeSort(co,div,k);
  Mergex(co,od,div,k);
  }
 }

float mdist2=FLT_MAX;
int p1,p2;

/* Nalezne nejbližší dva body */
void GetBest(bod co[],int od,int k)
 {
 if (od+1<k)
  {
  int div=(od+k)/2;
  float dist=sqrt(mdist2);
  float delx=co[div].x;
  float alen;
  int i,lleft,lright,ltested,atested;
  /* Nalezneme body v jednotlivých polovinách */
  GetBest(co,od,div);
  GetBest(co,div,k);
  /* Vybereme body, se kterými má smysl se zabývat */
  lleft=od;lright=div;
  for (i=od;i<div;i++) if (fabs(co[i].x-delx)<dist) temp[lleft++]=co[i];
  for (;i<k;i++) if (fabs(co[i].x-delx)<dist) temp[lright++]=co[i];
  ltested=div;
  temp[lright].y=1e30;
  /* Procházíme po řadě body na levé straně */
  for (i=od;i<lleft;i++)
   {
   /* Nalezneme dostatečně blízký bod na pravé straně */
   while (temp[ltested].y<temp[i].y-dist) ltested++;
   if (ltested==lright) break; /* Body došly? */
   /* Otestujeme, zda nějaký z bodů není blíže */
   for (atested=ltested;temp[atested].y<temp[i].y+dist;atested++)
    if ((alen=dist2(temp[i],temp[atested]))<mdist2)
     {
     p1=temp[i].id;p2=temp[atested].id;mdist2=alen;
     }
   }
  /* Sloučíme seznamy setříděné dle Y */
  Mergey(co,od,div,k);
  }
 }

int main(void)
 {
 int i,n;
 /* Načteme vstup */
 printf("Pocet vysilacu: ");
 scanf("%d",&n);
 for (i=0;i<n;i++)
  {
  printf("Souradnice vysilace cislo %d: ",i+1);
  scanf("%f %f",&body[i].x,&body[i].y);
  body[i].id=i+1;
  }
 MergeSort(body,0,n);
 GetBest(body,0,n);
 printf("Nejblize jsou vysilace %d a %d, vzdalenost %f.\n",p1,p2,sqrt(mdist2));
 return 0;
 }