W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Jack works as a jeweler. A beautiful diamond of extraordinary size has been shipped to his shop. There are two customers who would like to buy it, so Jack decided to cut the diamond into two pieces (not necessarily of equal masses) and sell each piece to one of the customers.
Diamonds are very hard and can only be cut by a saw with diamond blades. The cutting process is expensive and slow, as it takes about an hour to cut two millimeters. Jack can only afford making one cut along a single plane. Both pieces which he will receive are to be sold to the two customers.
Jack would like to make his customers as happy as possible. As the total mass of the pieces will obviously be equal to the mass of the whole diamond, Jack has decided to maximize the total number of faces in the two pieces. He does not know how to cut the diamond in such a way, so he asked you for help.
In the first line of the standard input there is a single integer (), the number of vertices of the diamond. Each of the following lines contains three integers (), separated by single spaces, and representing coordinates of the vertex of the diamond. The diamond is the smallest convex polyhedron, that contains all given vertices. None of those points lie in the interior the diamond and no four vertices are located in the same plane.
The first and only line of the standard output should contain one integer - the largest total number of faces of the two pieces obtained by cutting the diamond once only.
For the input data:
5 0 0 0 5 0 0 0 5 0 0 0 5 2 2 2
the correct result is:
14
Task author: Jakub Onufry Wojtaszczyk.