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 (
#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.
Marcin is peeling a potato. For simplicity, we assume that the potato is a convex polygon1, which edge is called a rind.
Marcin can perform straight cuts with his knife. With each cut, Marcin selects some straight line, along which a cut is being performed. After a cut is done, he throws away one of the parts of the potato. All points along the cut-line are also thrown away, so for instance when cutting along the line containing some edge belonging to the rind of the potato, that edge gets peeled.
A potato is said to be peeled only when it does not contain any point of the original rind. Marcin wants to perform as little work as possible when peeling the potato, which is why he would like to peel it with a limited number of cuts. Nevertheless, he wants to maximize the size of the peeled potato. What is the largest area of the pealed potato that can be obtained with at most cuts?
Write a program which:
In the first line of the standard input there are two integers () and (), separated by a single space and denoting the number of vertices of the polygon representing a potato under consideration and the maximal number of cuts that Marcin wants to perform to peel the potato. The following lines contain a description of the following vertices of the potato. They are specified in clockwise or anti-clockwise order. Each line contains two integers and , , representing coordinates of the following potato's vertex.
In the first and only line of the standard output your program should write one real number, written with exactly one digit after the dot and representing the largest possible area of the peeled potato that can be obtained with at most cuts. You should not round this number, the second and following digits after the dot do not impact the outcome.
For the input data:
5 3 0 0 3 1 6 4 3 7 0 8
the correct result is:
Sample potato can be optimally peeled with cuts in the way demonstrated above.
Task author: Marcin Pilipczuk.