2015 German Collegiate Programming Contest (GCPC)
Sophie loves to bake cakes and share them with friends. For the wedding of her best friend Bea she made a very special cake using only the best ingredients she could get and added a picture of the engaged couple on top of the cake. To make it even more special she did not make it round or square, but made a custom convex shape for the cake. Sophie decided to send the cake by a specialized carrier to the party. Unfortunately, the cake is a little too heavy for their default cake package and the overweight fees are excessive. Therefore, Sophie decides to remove some parts of the cake to make it a little lighter.
Sophie wants to cut the cake the following way: First, she chooses a real number s ≥ 2. For each vertex and each incident edge of the cake she marks where 1 / s of the edge's length is. Afterwards, she makes a direct cut between the two markings for each vertex and removes the vertex that way.
Sophie does not want to cut more from the cake than necessary for obvious reasons. Can you tell her how to choose s?
The first line contains a floating point number a and an integer n (0.25 ≤ a < 1, 3 ≤ n ≤ 100), where a denotes the ratio of the cake's weight allowed by the carrier and n the number of vertices of the cake. a will be specified with at most 7 digits after the decimal point.
Then follow n lines, each describing one of the cake's vertices with two integers
yi (0 ≤
108 for all 1 ≤ i ≤ n), the coordinates of the vertex. The vertices are given in the order in which they form a strictly convex shape.
You may safely assume that the weight is uniformly distributed over the area of the cake. Furthermore, it will always be possible to cut the cake with some 2 ≤ s ≤ 1000 such that the proportion of the remaining cake is a of the original weight.
Print a line containing s, the biggest value as specified above such that the remaining cake's weight is at most the proportion a of its original weight.
Your answer will be considered correct if the absolute error is at most
0.875 4 0 0 8 0 8 4 0 4
0.85 5 6 0 12 6 9 12 0 12 3 3
0.999998 4 20008 10000 15004 15005 10001 20009 15005 15004