fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <limits>
  6. #include <iomanip>
  7. using namespace std;
  8.  
  9. struct wynik //struktura wyniku (odleglosc,pozycje na wejsciu punktu 1 i 2)
  10. 	{
  11. 	double distance;
  12. 	int p1;
  13. 	int p2;
  14. 	};
  15.  
  16. double odleglosc(pair<int,int> *a, pair<int,int> *b) //odleglosc pomiedzy dwoma punktami
  17. 	{return sqrt((a->first-b->first)*(a->first-b->first)+(a->second-b->second)*(a->second-b->second));}
  18.  
  19. bool my_compare_X(pair<int,int> *a,pair<int,int> *b) //funktor greater dla OX
  20. 	{return a->first==b->first?a->second<b->second:a->first<b->first;}
  21.  
  22. bool my_compare_Y(pair<int,int> *a,pair<int,int> *b) //funktor greater dla OY
  23. 	{return a->second==b->second?a->first<b->first:a->second<b->second;}
  24.  
  25. //Globalne żeby były widoczne wewnątrz rekurencji bez kopiowania ani odkładania wskaźnika
  26. vector<pair<int,int>>Punkty; //tablica punktów
  27. vector<pair<int,int>*>X; //wektor ze wskaźnikami do punktów do sort po x
  28. wynik *wyn=new wynik{numeric_limits<double>::max(),-1,-1};
  29.  
  30. void Filtruj(vector<pair<int,int>*>&Set,int p)
  31. 	{
  32. 	int s=0;
  33. 	for(int i=0;i<Set.size();i++)
  34. 		if(odleglosc(Set[i],new pair<int,int>(p,Set[i]->second))<=wyn->distance)Set[s++]=Set[i];
  35. 	Set.resize(s);
  36. 	}
  37.  
  38. void Najblizsze_punkty(int p,int k,vector<pair<int,int>*>Y)
  39. 	{
  40. 	if(k-p>1)
  41. 		{
  42. 		vector<pair<int,int>*>XL,XP; //wskazniki na zbiory lewy i prawy
  43. 		int srodek=(k+p-1)/2; //X[srodek] jest osią podzialu
  44. 		for(int i=0;i<Y.size();i++)
  45. 			my_compare_X(X[srodek],Y[i])?XP.push_back(Y[i]):XL.push_back(Y[i]);
  46.  
  47. 		Najblizsze_punkty(p,srodek+1,XL); //czesc lewa
  48. 		Najblizsze_punkty(srodek+1,k,XP); //czesc prawa
  49. 		Filtruj(XL,X[srodek]->first);	//usuwanie punktow odleglych dalej niz distance
  50. 		Filtruj(XP,X[srodek]->first);
  51. 		//przeglad punktow pomiedzy podzialami o odleglosci mniejszej niz distance
  52.  
  53. 		int p=0;
  54. 		for(int i=0;i<XL.size();i++)
  55. 			{
  56. 			while(p<XP.size()-1&&XP[p+1]->second<XL[i]->second)p++;
  57. 			int size=XP.size();
  58. 			for(int x=max(0,p-2);x<=min(size-1,p+1);x++)
  59. 				{
  60. 				if(wyn->distance>odleglosc(XL[i],XP[x]))
  61. 					{
  62. 					wyn->distance=odleglosc(XL[i],XP[x]);
  63. 					wyn->p1=min(int(XL[i]-&(Punkty[0])),int(XP[x]-&(Punkty[0])));
  64. 					wyn->p2=max(int(XP[x]-&(Punkty[0])),int(XL[i]-&(Punkty[0])));
  65. 					}
  66. 				}
  67. 			}
  68. 		}
  69. 	}
  70.  
  71. wynik* Algorytm()
  72. 	{
  73. 	vector<pair<int,int>*>Y; //wektor ze wskaźnikami do punktów do sort po y
  74.  
  75. 	for(int i=0;i<Punkty.size();i++)
  76. 		{
  77. 		X.push_back(&(Punkty[i])); //wrzuca wskaźniki do punktów z Punkty do X
  78. 		Y.push_back(&(Punkty[i])); //wrzuca wskaźniki do punktów z Punkty do Y
  79. 		}
  80.  
  81. 	sort(X.begin(),X.end(),my_compare_X); //sortuje punkty po wspolrzednej x
  82. 	sort(Y.begin(),Y.end(),my_compare_Y); //sortuje punkty po wspolrzednej y
  83.  
  84. 	for(int i=1;i<X.size();i++) //jeśli są duplikaty to min odleglosc to 0
  85. 		{
  86. 		if(X[i]->first==X[i-1]->first && X[i]->second==X[i-1]->second) //czy duplikat
  87. 			{
  88. 			wyn->distance=0;
  89. 			wyn->p1=min(int(X[i-1]-&(Punkty[0])),int(X[i]-&(Punkty[0])));
  90. 			wyn->p2=max(int(X[i]-&(Punkty[0])),int(X[i-1]-&(Punkty[0])));
  91. 			return wyn;
  92. 			}
  93. 		}
  94. 	//glowny algorytm, bedziemy dzielili wzgledem prostych prostopadlych do OX
  95. 	Najblizsze_punkty(0,Y.size(),Y);
  96.  
  97. 	return wyn; //zwracanie struktury wynikowej
  98. 	}
  99.  
  100. int main() 
  101. 	{
  102. 	int t,a,b;
  103. 	cin>>t;
  104. 	for(int i=0;i<t;i++)
  105. 		{
  106. 		cin>>a>>b;
  107. 		Punkty.push_back({a,b});
  108. 		}
  109. 	wynik *W=Algorytm();
  110. 	cout<<W->p1<<" "<<W->p2<<" "<<fixed<<setprecision(6)<<W->distance<<endl;
  111. 	}
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
4
1 4
1 6
1 2
1 5
stdout
copy 
1 3 1.000000
https://ideone.com/ba8XqG
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!