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