Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_12_17 - parkrun Fraktalocja

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 ≤ 106).

W kolejnych n wierszach współrzędne drzew w postaci dwóch liczb całkowitych x, y (|x| ≤ 105, |y| ≤ 105). 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

Dodane przez:Marcin Kasprowicz
Data dodania:2021-01-11
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.