Algorytmy 2
Otoczka wypukła
Dany jest zbiór $n$ punktów na płaszczyźnie. Wyznacz otoczkę wypukłą tych punktów.
Wejście
Pierwsza linia wejściowa zawiera liczbę naturalną $n$: liczbę punktów. Następne $n$ linii opisuje kolejne punkty. Każda linia zawiera dwie liczby całkowite $x$ i $y$: współrzędne punktu. Można założyć, że punkty się nie powtarzają, a pole powierzchni otoczki jest dodatnie.
Wyjście
Najpierw wypisz liczbę całkowitą $k$: liczbę punktów leżących na brzegu otoczki wypukłej. Następnie wypisz $k$ linii opisujących punkty. Punkty możesz wypisać w dowolnej kolejności. Wypisz wszystkie punkty leżące na brzegu otoczki wypukłej.
Ograniczenia
- $3 \le n \le 2 \cdot 10^5$
- $-10^9 \le x, y \le 10^9$
Przykłady
Wejście 1
6
2 1
2 5
3 3
4 3
4 4
6 3
Wyjście 1
4
2 1
2 5
4 4
6 3