#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <limits>
using namespace std;
struct wynik //struktura wyniku (odleglosc,pozycje wejsciowe punktu 1 i 2)
{
double distance;
int p1;
int p2;
}wyn={numeric_limits<double>::max(),-1,-1}; //to będzie nasz wynik
struct punkt //struktura punktu
{
int x;
int y;
punkt(int a=0,int b=0){this->x=a;this->y=b;}
};
punkt Punkty[50005]; //tablica wejściowa punktów
punkt *X[50005]; //tablica wskaźników na punkty
int t,a,b; //t to liczba punktów na wejściu, a i b to wspolrzedne przy czytaniu
double odleglosc(punkt *a, punkt *b) //odleglosc pomiedzy dwoma punktami
{return (a->x-b->x)*(a->x-b->x)+(a->y-b->y)*(a->y-b->y);}
bool my_compare_X(punkt *a,punkt *b) //funktor dla porzadku liniowego OX
{return a->x==b->x?a->y<b->y:a->x<b->x;}
bool my_compare_Y(punkt *a,punkt *b) //funktor dla porzadku liniowego OY
{return a->y==b->y?a->x<b->x:a->y<b->y;}
void Najblizsze_punkty(int p,int k,punkt **Y,int size)
{
if(k-p>1)
{
punkt** XL=new punkt*[size/2+1]; //wskazniki na zbiory lewy i prawy
punkt** XP=new punkt*[size/2+1];
int srodek=(k+p-1)/2,x=0,y=0; //X[srodek] jest osią podzialu
for(int i=0;i<size;i++)
{
if(my_compare_X(X[srodek],Y[i])) //podzial na dwie czesci zbioru
XP[x++]=Y[i];
else
XL[y++]=Y[i];
}
//x i y stanowią rozmiary podczęści tablicy
Najblizsze_punkty(p,srodek+1,XL,y); //czesc lewa
Najblizsze_punkty(srodek+1,k,XP,x); //czesc prawa
punkt** Y2=new punkt*[size+1]; //tablica wskaźników na punkty odlegle mniej niż distance
int y2=0;
for(int i=0;i<size;i++)
if(odleglosc(Y[i],new punkt(X[srodek]->x,Y[i]->y))<=wyn.distance)Y2[y2++]=Y[i];
//przeglad punktow pomiedzy podzialami o odleglosci mniejszej niz distance
for(int i=0;i<y2;i++)
{
for(int j=i+1;j<=min(i+7,y2-1);j++)
{
if(wyn.distance>odleglosc(Y2[i],Y2[j]))
{
wyn.distance=odleglosc(Y2[i],Y2[j]);
wyn.p1=min(int(Y2[i]-&(Punkty[0])),int(Y2[j]-&(Punkty[0])));
wyn.p2=max(int(Y2[j]-&(Punkty[0])),int(Y2[i]-&(Punkty[0])));
}
}
}
delete[] Y2;
delete[] XL;
delete[] XP;
}
}
int main()
{
punkt **Y=new punkt*[50005]; //tablica ze wskaźnikami do punktów do sort po y
cin>>t;
for(int i=0;i<t;i++)
{
cin>>Punkty[i].x>>Punkty[i].y;
X[i]=&(Punkty[i]); //wrzuca wskaźniki do punktów z Punkty do X
Y[i]=&(Punkty[i]); //wrzuca wskaźniki do punktów z Punkty do Y
}
sort(X,X+t,my_compare_X); //sortuje punkty po wspolrzednej x
sort(Y,Y+t,my_compare_Y); //sortuje punkty po wspolrzednej y
for(int i=1;i<t;i++) //jeśli są duplikaty to min odleglosc to 0
{
if(X[i]->x==X[i-1]->x&&X[i]->y==X[i-1]->y) //czy duplikat
{
wyn.distance=0;
//pozycje wyznaczane za pomocą odległosci wskaźnika od Offsetu na Punkty
wyn.p1=min(int(X[i-1]-&(Punkty[0])),int(X[i]-&(Punkty[0])));
wyn.p2=max(int(X[i]-&(Punkty[0])),int(X[i-1]-&(Punkty[0])));
goto koniec; //idź 4 linijki niżej
}
}
Najblizsze_punkty(0,t,Y,t);
koniec:
cout<<wyn.p1<<" "<<wyn.p2<<" "<<fixed<<setprecision(6)<<sqrt(wyn.distance);
delete[] Y;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8bGltaXRzPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RydWN0IHd5bmlrIC8vc3RydWt0dXJhIHd5bmlrdSAob2RsZWdsb3NjLHBvenljamUgd2Vqc2Npb3dlIHB1bmt0dSAxIGkgMikKCXsKCWRvdWJsZSBkaXN0YW5jZTsKCWludCBwMTsKCWludCBwMjsKCX13eW49e251bWVyaWNfbGltaXRzPGRvdWJsZT46Om1heCgpLC0xLC0xfTsgLy90byBixJlkemllIG5hc3ogd3luaWsKCnN0cnVjdCBwdW5rdCAvL3N0cnVrdHVyYSBwdW5rdHUKCXsKCWludCB4OwoJaW50IHk7CglwdW5rdChpbnQgYT0wLGludCBiPTApe3RoaXMtPng9YTt0aGlzLT55PWI7fQoJfTsKCQpwdW5rdCBQdW5rdHlbNTAwMDVdOyAvL3RhYmxpY2Egd2VqxZtjaW93YSBwdW5rdMOzdwpwdW5rdCAqWFs1MDAwNV07IC8vdGFibGljYSB3c2thxbpuaWvDs3cgbmEgcHVua3R5CmludCB0LGEsYjsgLy90IHRvIGxpY3piYSBwdW5rdMOzdyBuYSB3ZWrFm2NpdSwgYSBpIGIgdG8gd3Nwb2xyemVkbmUgcHJ6eSBjenl0YW5pdQkKCQpkb3VibGUgb2RsZWdsb3NjKHB1bmt0ICphLCBwdW5rdCAqYikgLy9vZGxlZ2xvc2MgcG9taWVkenkgZHdvbWEgcHVua3RhbWkKCXtyZXR1cm4gKGEtPngtYi0+eCkqKGEtPngtYi0+eCkrKGEtPnktYi0+eSkqKGEtPnktYi0+eSk7fQoKYm9vbCBteV9jb21wYXJlX1gocHVua3QgKmEscHVua3QgKmIpIC8vZnVua3RvciBkbGEgcG9yemFka3UgbGluaW93ZWdvIE9YCgl7cmV0dXJuIGEtPng9PWItPng/YS0+eTxiLT55OmEtPng8Yi0+eDt9Cgpib29sIG15X2NvbXBhcmVfWShwdW5rdCAqYSxwdW5rdCAqYikgLy9mdW5rdG9yIGRsYSBwb3J6YWRrdSBsaW5pb3dlZ28gT1kKCXtyZXR1cm4gYS0+eT09Yi0+eT9hLT54PGItPng6YS0+eTxiLT55O30KCQp2b2lkIE5hamJsaXpzemVfcHVua3R5KGludCBwLGludCBrLHB1bmt0ICoqWSxpbnQgc2l6ZSkKCXsKCWlmKGstcD4xKQoJCXsKCQlwdW5rdCoqIFhMPW5ldyBwdW5rdCpbc2l6ZS8yKzFdOyAvL3dza2F6bmlraSBuYSB6YmlvcnkgbGV3eSBpIHByYXd5CgkJcHVua3QqKiBYUD1uZXcgcHVua3QqW3NpemUvMisxXTsgCgkJaW50IHNyb2Rlaz0oaytwLTEpLzIseD0wLHk9MDsgLy9YW3Nyb2Rla10gamVzdCBvc2nEhSBwb2R6aWFsdQoJCQoJCWZvcihpbnQgaT0wO2k8c2l6ZTtpKyspCgkJCXsKCQkJaWYobXlfY29tcGFyZV9YKFhbc3JvZGVrXSxZW2ldKSkgLy9wb2R6aWFsIG5hIGR3aWUgY3plc2NpIHpiaW9ydQoJCQkJWFBbeCsrXT1ZW2ldOwoJCQllbHNlCgkJCQlYTFt5KytdPVlbaV07CgkJCX0KCQkKCQkvL3ggaSB5IHN0YW5vd2nEhSByb3ptaWFyeSBwb2RjesSZxZtjaSB0YWJsaWN5IAoJCQoJCU5hamJsaXpzemVfcHVua3R5KHAsc3JvZGVrKzEsWEwseSk7IC8vY3plc2MgbGV3YQoJCU5hamJsaXpzemVfcHVua3R5KHNyb2RlaysxLGssWFAseCk7IC8vY3plc2MgcHJhd2EKCQkKCQlwdW5rdCoqIFkyPW5ldyBwdW5rdCpbc2l6ZSsxXTsgLy90YWJsaWNhIHdza2HFum5pa8OzdyBuYSBwdW5rdHkgb2RsZWdsZSBtbmllaiBuacW8IGRpc3RhbmNlCgkJaW50IHkyPTA7CgkJZm9yKGludCBpPTA7aTxzaXplO2krKykKCQkJaWYob2RsZWdsb3NjKFlbaV0sbmV3IHB1bmt0KFhbc3JvZGVrXS0+eCxZW2ldLT55KSk8PXd5bi5kaXN0YW5jZSlZMlt5MisrXT1ZW2ldOwoJCQoJCS8vcHJ6ZWdsYWQgcHVua3RvdyBwb21pZWR6eSBwb2R6aWFsYW1pIG8gb2RsZWdsb3NjaSBtbmllanN6ZWogbml6IGRpc3RhbmNlCgkJZm9yKGludCBpPTA7aTx5MjtpKyspCgkJCXsKCQkJZm9yKGludCBqPWkrMTtqPD1taW4oaSs3LHkyLTEpO2orKykKCQkJCXsKCQkJCWlmKHd5bi5kaXN0YW5jZT5vZGxlZ2xvc2MoWTJbaV0sWTJbal0pKQoJCQkJCXsKCQkJCQl3eW4uZGlzdGFuY2U9b2RsZWdsb3NjKFkyW2ldLFkyW2pdKTsKCQkJCQl3eW4ucDE9bWluKGludChZMltpXS0mKFB1bmt0eVswXSkpLGludChZMltqXS0mKFB1bmt0eVswXSkpKTsKCQkJCQl3eW4ucDI9bWF4KGludChZMltqXS0mKFB1bmt0eVswXSkpLGludChZMltpXS0mKFB1bmt0eVswXSkpKTsKCQkJCQl9CgkJCQl9CgkJCX0KCQlkZWxldGVbXSBZMjsKCQlkZWxldGVbXSBYTDsKCQlkZWxldGVbXSBYUDsKCQl9Cgl9CgppbnQgbWFpbigpIAoJewoJcHVua3QgKipZPW5ldyBwdW5rdCpbNTAwMDVdOyAvL3RhYmxpY2EgemUgd3NrYcW6bmlrYW1pIGRvIHB1bmt0w7N3IGRvIHNvcnQgcG8geQoJY2luPj50OwoJZm9yKGludCBpPTA7aTx0O2krKykKCQl7CgkJY2luPj5QdW5rdHlbaV0ueD4+UHVua3R5W2ldLnk7CgkJWFtpXT0mKFB1bmt0eVtpXSk7IC8vd3J6dWNhIHdza2HFum5pa2kgZG8gcHVua3TDs3cgeiBQdW5rdHkgZG8gWAoJCVlbaV09JihQdW5rdHlbaV0pOyAvL3dyenVjYSB3c2thxbpuaWtpIGRvIHB1bmt0w7N3IHogUHVua3R5IGRvIFkKCQl9CgkKCXNvcnQoWCxYK3QsbXlfY29tcGFyZV9YKTsgLy9zb3J0dWplIHB1bmt0eSBwbyB3c3BvbHJ6ZWRuZWogeAoJc29ydChZLFkrdCxteV9jb21wYXJlX1kpOyAvL3NvcnR1amUgcHVua3R5IHBvIHdzcG9scnplZG5laiB5CgkKCWZvcihpbnQgaT0xO2k8dDtpKyspIC8vamXFm2xpIHPEhSBkdXBsaWthdHkgdG8gbWluIG9kbGVnbG9zYyB0byAwCgkJewoJCWlmKFhbaV0tPng9PVhbaS0xXS0+eCYmWFtpXS0+eT09WFtpLTFdLT55KSAvL2N6eSBkdXBsaWthdAoJCQl7CgkJCXd5bi5kaXN0YW5jZT0wOwoJCQkvL3BvenljamUgd3l6bmFjemFuZSB6YSBwb21vY8SFIG9kbGVnxYJvc2NpIHdza2HFum5pa2Egb2QgT2Zmc2V0dSBuYSBQdW5rdHkKCQkJd3luLnAxPW1pbihpbnQoWFtpLTFdLSYoUHVua3R5WzBdKSksaW50KFhbaV0tJihQdW5rdHlbMF0pKSk7CgkJCXd5bi5wMj1tYXgoaW50KFhbaV0tJihQdW5rdHlbMF0pKSxpbnQoWFtpLTFdLSYoUHVua3R5WzBdKSkpOwoJCQlnb3RvIGtvbmllYzsgLy9pZMW6IDQgbGluaWpraSBuacW8ZWoKCQkJfQoJCX0KCU5hamJsaXpzemVfcHVua3R5KDAsdCxZLHQpOwoJa29uaWVjOgoJY291dDw8d3luLnAxPDwiICI8PHd5bi5wMjw8IiAiPDxmaXhlZDw8c2V0cHJlY2lzaW9uKDYpPDxzcXJ0KHd5bi5kaXN0YW5jZSk7CglkZWxldGVbXSBZOwoJfQ==