Diament [B]

Limit pamięci: 32 MB

Józek jest jubilerem. Do jego sklepu trafił wyjątkowo piękny diament o niespotykanych rozmiarach. Józek ma dwóch klientów chętnych do kupna tego diamentu. Dlatego też zdecydował, że przetnie diament na dwie części (niekoniecznie o równych masach) i sprzeda po jednej z nich każdemu z klientów.

Diament jest bardzo twardy i tnie się go tarczami z diamentowymi ostrzami, z prędkością około dwóch milimetrów na godzinę. Jest to więc proces kosztowny i czasochłonny. Józka stać na wykonanie tylko jednego cięcia wzdłuż dowolnej płaszczyzny. Wykonane części będzie musiał dostarczyć klientom.

Józek chce, żeby klienci byli jak najbardziej zadowoleni. Jako że łączna masa części diamentu, które dostaną, będzie oczywiście równa masie pierwotnego diamentu, Józek postanowił zmaksymalizować łączną liczbę ścianek w obydwu częściach. Niestety nie wie, jak tego dokonać, więc prosi Cię o pomoc.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita (), oznaczająca liczbę wierzchołków diamentu. W następnych wierszach znajdują się po trzy liczby całkowite (), pooddzielane pojedynczymi odstępami i oznaczające współrzędne -tego wierzchołka diamentu. Diament jest najmniejszym wielościanem wypukłym zawierającym te punktów. Żaden z punktów nie leży we wnętrzu diamentu, ani też żadne cztery punkty nie leżą na jednej płaszczyźnie.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą, oznaczającą największą łączną liczbę ścianek, którą mogą mieć obydwa kawałki diamentu po wykonaniu jednego cięcia.

Przykład

Dla danych wejściowych:

5
0 0 0
5 0 0
0 5 0
0 0 5
2 2 2

poprawną odpowiedzią jest:

14

Autor zadania: Jakub Onufry Wojtaszczyk.