Sortowanie kątowe (kątowe zamiatanie)

powrót

Zamiatanie kątowe polega na posortowaniu punków na układzie współrzędnych względem najniżej położonego punktu w taki sposób, jak wskazówka zegara, zakotwiczona w punkcie P, wskazująca początkowo godzinę trzecią i poruszająca się w kierunku przeciwnym do wskazówek będzie "zbierać" kolejne napotkane punkty. Patrząc na rysunek poniżej, zebrane punkty będą w kolejności A, B, C, D, E, F, G, H, I, J oraz K.

Do posortowania użyjemy funkcji kotangens dla kolejnych kątów wyznaczanych przez wskazówkę zegara oraz prostą równoległą do osi OX przechodzącą przez punkt P. Zauważ, że dziedzina kąta α zawiera się w przedziale$$\alpha \in \left<0^\circ;180^\circ\right>$$.

Funkcja tangens jest ciągła i malejąca w przedziale $$\alpha \in \left(0^\circ;180^\circ\right)$$ oraz nie istnieje dla 0 i 180 stopni (przy definiowaniu porównania dla funkcji sortującej możemy to łatwo obejść).

Sortowanie wykonamy według następującego schematu: 

• wcześniej będzie punkt, który ma mniejszy kąt α
• jeśli dla pewnych dwóch punktów otrzymamy ten sam kąt, wybierz ten, który ma mniejszą odciętą (mniejszy x)

Załóżmy, że punkt: $$P = (x, y)$$oraz kolejne punkty określamy współrzędnymi $$P_i=(x_i,y_i)$$Żeby określić, który kąt jest większy, między dwoma różnymi punktami $$(x_i,y_i)$$i$$(x_j,y_j)$$wystarczy sprawdzić warunek $$\frac{x_i-x}{y_i-y}<\frac{x_j-x}{y_j-y}$$(nie zadziała to dla kąta 0 i 180 stopni). Aby uniknąć problemów z zaokrąglaniem i dzieleniem przez zero użyjemy alternatywnego zapisu:

$$(x_i-x)\cdot(y_j-y)<(x_j-x)\cdot(y_i-y)$$

Program

#include<bits/stdc++.h>
using namespace std;
#define pkt pair<int, int>
//punkt, wzgledem ktorego bedziemy sortowac
pair <int, int> start;

//funkcja porównująca punkty
bool porownaj(pair <int, int> A, pair <int, int> B)
{
	//ustawienie punktu P jako pierwszy w tablicy
	if(A==start)return 1;
	if(B==start)return 0;
	//--------------------------------------------
	
	//jesli dla dwoch punkow kat jest taki sam, to najpierw
	//wez ten, ktory ma mniejsza wspolrzedna x
	if((A.second-start.second)*(B.first-start.first) == 
	(A.first-start.first)*(B.second-start.second))
		return A.first<B.first;
	return (A.second-start.second)*(B.first-start.first) <
	(A.first-start.first)*(B.second-start.second);
}

int main()
{
	int n;
	cout<<"Podaj liczbe punktow do posorotwania: ";
	cin>>n;
	
	//tworzymy wektor na n punktow
	vector <pair<int, int> > P(n);
	
	for(int i=0; i<n; i++)
	{
		cin>>P[i].first>>P[i].second; //P(x, y) = (P.first, P.second)
		//szukamy punktu najnizej połozonego, a w przypadku remisu
		//najbardziej na lewo
		if(i==0)
			start = P[i];
		else
			if(P[i].second == start.second)
				start.first = min(P[i].first, start.first);
			else 
				if(P[i].second < start.second)
					start = P[i];
	}
	
	//sortowanie punktów w czasie O(n log n)
	sort(P.begin(), P.end(), porownaj);

	cout<<"Wynik sortowania: \n";

	//wypisanie puntków
	for(int i=0;i<P.size();i++)
		cout<<P[i].first<<' '<<P[i].second<<endl;
		
	return 0;
}

Dane wejściowe i wyjściowe

Podaj liczbe punktow do posorotwania: 5
1 1
2 1
4 -1
-2 -5
2 3
Wynik sortowania:
-2 -5
4 -1
2 1
1 1
2 3