Łamane płaskie

Limit pamięci: 32 MB

Rozważmy kartezjański układ współrzędnych narysowany na kartce papieru. Łamaną płaską w tym układzie nazywamy łamaną, którą można wykreślić prowadząc ołówek bez odrywania od papieru w kierunku od lewej do prawej strony kartki i taką, że każda prosta zawierająca odcinek łamanej jest nachylona do osi pod kątem należącym do przedziału domkniętego .

Na kartce narysowano różnych punktów o obu współrzędnych całkowitych. Jaka jest najmniejsza liczba łamanych płaskich, które należałoby wykreślić, żeby każdy z n punktów należał do co najmniej jednej z nich?

Przykład

Dla punktów o współrzędnych , , , , , najmniejszą liczbą łamanych płaskich pokrywających te punkty jest .

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia liczbę punktów i ich współrzędne;
• oblicza najmniejszą liczbę łamanych płaskich, które należałoby wykreślić, żeby pokryły one wszystkie punkty;
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się dodatnia liczba całkowita nie większa od . Jest to liczba punktów. W kolejnych wierszach znajdują się współrzędne punktów. Każdy wiersz zawiera dwie liczby całkowite oddzielone pojedynczym odstępem, , . Liczby w wierszu , , są współrzędnymi -tego punktu.

Wyjście

Twój program powinien zapisać jedną liczbę całkowitą w pierwszym i jedynym wierszu standardowego wyjścia. Tą liczbą powinna być najmniejsza liczba łamanych płaskich, które należy wykreślić, żeby pokryć wszystkie dane punkty.

Przykład

Dla danych wejściowych:

6
1 6
10 8
1 5
2 20
4 4
6 2

poprawną odpowiedzią jest:

3

Autor zadania: Krzysztof Sobusiak.