In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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.
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.
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.
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.