fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <iomanip>
  5. #include <limits>
  6. using namespace std;
  7.  
  8. struct wynik //struktura wyniku (odleglosc,pozycje wejsciowe punktu 1 i 2)
  9. 	{
  10. 	double distance;
  11. 	int p1;
  12. 	int p2;
  13. 	}wyn={numeric_limits<double>::max(),-1,-1}; //to będzie nasz wynik
  14.  
  15. struct punkt //struktura punktu
  16. 	{
  17. 	int x;
  18. 	int y;
  19. 	punkt(int a=0,int b=0){this->x=a;this->y=b;}
  20. 	};
  21.  
  22. punkt Punkty[50005]; //tablica wejściowa punktów
  23. punkt *X[50005]; //tablica wskaźników na punkty
  24. int t,a,b; //t to liczba punktów na wejściu, a i b to wspolrzedne przy czytaniu	
  25.  
  26. double odleglosc(punkt *a, punkt *b) //odleglosc pomiedzy dwoma punktami
  27. 	{return (a->x-b->x)*(a->x-b->x)+(a->y-b->y)*(a->y-b->y);}
  28.  
  29. bool my_compare_X(punkt *a,punkt *b) //funktor dla porzadku liniowego OX
  30. 	{return a->x==b->x?a->y<b->y:a->x<b->x;}
  31.  
  32. bool my_compare_Y(punkt *a,punkt *b) //funktor dla porzadku liniowego OY
  33. 	{return a->y==b->y?a->x<b->x:a->y<b->y;}
  34.  
  35. void Najblizsze_punkty(int p,int k,punkt **Y,int size)
  36. 	{
  37. 	if(k-p>1)
  38. 		{
  39. 		punkt** XL=new punkt*[size/2+1]; //wskazniki na zbiory lewy i prawy
  40. 		punkt** XP=new punkt*[size/2+1]; 
  41. 		int srodek=(k+p-1)/2,x=0,y=0; //X[srodek] jest osią podzialu
  42.  
  43. 		for(int i=0;i<size;i++)
  44. 			{
  45. 			if(my_compare_X(X[srodek],Y[i])) //podzial na dwie czesci zbioru
  46. 				XP[x++]=Y[i];
  47. 			else
  48. 				XL[y++]=Y[i];
  49. 			}
  50.  
  51. 		//x i y stanowią rozmiary podczęści tablicy 
  52.  
  53. 		Najblizsze_punkty(p,srodek+1,XL,y); //czesc lewa
  54. 		Najblizsze_punkty(srodek+1,k,XP,x); //czesc prawa
  55.  
  56. 		punkt** Y2=new punkt*[size+1]; //tablica wskaźników na punkty odlegle mniej niż distance
  57. 		int y2=0;
  58. 		for(int i=0;i<size;i++)
  59. 			if(odleglosc(Y[i],new punkt(X[srodek]->x,Y[i]->y))<=wyn.distance)Y2[y2++]=Y[i];
  60.  
  61. 		//przeglad punktow pomiedzy podzialami o odleglosci mniejszej niz distance
  62. 		for(int i=0;i<y2;i++)
  63. 			{
  64. 			for(int j=i+1;j<=min(i+7,y2-1);j++)
  65. 				{
  66. 				if(wyn.distance>odleglosc(Y2[i],Y2[j]))
  67. 					{
  68. 					wyn.distance=odleglosc(Y2[i],Y2[j]);
  69. 					wyn.p1=min(int(Y2[i]-&(Punkty[0])),int(Y2[j]-&(Punkty[0])));
  70. 					wyn.p2=max(int(Y2[j]-&(Punkty[0])),int(Y2[i]-&(Punkty[0])));
  71. 					}
  72. 				}
  73. 			}
  74. 		delete[] Y2;
  75. 		delete[] XL;
  76. 		delete[] XP;
  77. 		}
  78. 	}
  79.  
  80. int main() 
  81. 	{
  82. 	punkt **Y=new punkt*[50005]; //tablica ze wskaźnikami do punktów do sort po y
  83. 	cin>>t;
  84. 	for(int i=0;i<t;i++)
  85. 		{
  86. 		cin>>Punkty[i].x>>Punkty[i].y;
  87. 		X[i]=&(Punkty[i]); //wrzuca wskaźniki do punktów z Punkty do X
  88. 		Y[i]=&(Punkty[i]); //wrzuca wskaźniki do punktów z Punkty do Y
  89. 		}
  90.  
  91. 	sort(X,X+t,my_compare_X); //sortuje punkty po wspolrzednej x
  92. 	sort(Y,Y+t,my_compare_Y); //sortuje punkty po wspolrzednej y
  93.  
  94. 	for(int i=1;i<t;i++) //jeśli są duplikaty to min odleglosc to 0
  95. 		{
  96. 		if(X[i]->x==X[i-1]->x&&X[i]->y==X[i-1]->y) //czy duplikat
  97. 			{
  98. 			wyn.distance=0;
  99. 			//pozycje wyznaczane za pomocą odległosci wskaźnika od Offsetu na Punkty
  100. 			wyn.p1=min(int(X[i-1]-&(Punkty[0])),int(X[i]-&(Punkty[0])));
  101. 			wyn.p2=max(int(X[i]-&(Punkty[0])),int(X[i-1]-&(Punkty[0])));
  102. 			goto koniec; //idź 4 linijki niżej
  103. 			}
  104. 		}
  105. 	Najblizsze_punkty(0,t,Y,t);
  106. 	koniec:
  107. 	cout<<wyn.p1<<" "<<wyn.p2<<" "<<fixed<<setprecision(6)<<sqrt(wyn.distance);
  108. 	delete[] Y;
  109. 	}
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
5
0 0
0 1
1 0
-1 0
0 -1
stdout
copy 
0 4 1.000000
https://ideone.com/IklCr4
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!