FRAKTAL - konkurs programistyczny

Parkrun to darmowe biegi na 5 kilometrów, które odbywają się w każdą sobotę o godzinie 9:00, w ponad 1500 lokalizacjach na całym świecie. Trasę można pokonać dowolnym sposobem: biegnąc, truchtając czy spacerując. Można ze sobą zabrać dziecko w wózku lub czworonożnego przyjaciela.

Od tej chwili jesteś koordynatorem parkrun we Fraktalocji i odpowiadasz za wyznaczenie trasy. Oto co musisz zrobić:

• Wybrać las, w którym będzie odbywał się bieg.
• Ogrodzić cały las mocując biało-czerwoną taśmę do drzew, tak aby utworzony został wielokąt wypukły. Taśma powinna być przymocowana zarówno do drzew będących wierzchołkami wielokąta jak i do drzew należących do jego boków.
• Ogrodzić wszystkie drzewa, do których nie została przymocowana biało-czerwona taśma, taśmą żółto-czarną, tak aby utworzony został wielokąt wypukły.

Trasa biegu to obszar pomiędzy taśmami. W związku z pandemią COVID-19 we Fraktalocji również wprowadzono ograniczenia. W biegu może wziąć udział maksymalnie podłoga(p / 4) zawodników, gdzie p to pole powierzchni trasy, a podłoga(x) oznacza największą liczbę całkowitą nie większą niż x.

Twoim zadaniem jest obliczenie maksymalnej dopuszczalnej liczby uczestników parkrun Fraktalocja. Powodzenia!

Wejście

W pierwszym wierszu jedna liczba naturalna n określająca liczbę drzew (6 ≤ n ≤ 10⁶).

W kolejnych n wierszach współrzędne drzew w postaci dwóch liczb całkowitych x, y (|x| ≤ 10⁵, |y| ≤ 10⁵). Gwarantujemy, że żadne dwa drzewa nie mają tych samych współrzędnych oraz, że utworzenie wielokątów wypukłych wyznaczonych przez taśmy jest możliwe.

Wyjście

Na wyjściu należy wypisać maksymalną dopuszczalną liczbę uczestników parkrun Fraktalocja.

Przykład

Wejście:

7
1 1
-1 1
0 0
-1 -1
1 -1
2 2
-2 2

Wyjście:

2