In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#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.
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:
Task author: Jakub Onufry Wojtaszczyk.