An oft-forgotten part of a well-rounded software engineer’s training is those long but vital months spent learning the art of shipwrighting.
Modern boats, as we know, are superbly safe, to the point that they are nigh unsinkable. Even in a head-on collision the ship can be saved by a system of bulkheads, reinforced vertical sections inside the structure designed to prevent ingressed water from spreading to other sections.
A splendid new ship of the line has had a team of talented artists hard at work reticulating the finest splines for use in this vessel. However, not being concerned with such details, they have left out the placements of the bulkheads as an exercise for their readers.
This is where you can help. First, we need to find how many bulkheads we can fit in the ship. Second, the exact placements of the bulkheads need to be found.
One line containing an integer $C$ ($10 \le C \le 10^9$), the minimum area of a bulkhead section.
One line containing an integer $N$ ($3 \le N \le 10^5$), the number of vertices in the artists’ design for the boat.
$N$ unique lines, each containing two integers: $x$ and $y$ ($-10^5 \le x, y \le 10^5$), the coordinates of the vertices from the hull in counter-clockwise winding order.
The shape of the boat never doubles back on itself horizontally; that is to say, if a vertical line is drawn through the cross-section, no matter where, it will always pass through the boat exactly once—never twice—however it may run along one or more edges.
It is guaranteed that it is always possible to fit at least one bulkhead section into the ship.
One line containing one integer, $M$: the maximum number of bulkhead sections that can be created. It is guaranteed that $M$ is between $1$ and $100$.
$M-1$ lines, each containing one real number: the $X$-coordinate of the placement of a bulkhead such that the sections defined by it have equal area to all the others. Bulkhead placements must be given in increasing order of $X$.
All output must be accurate to an absolute or relative error of at most $10^{-6}$.
Sample Input 1 | Sample Output 1 |
---|---|
50 4 110 10 80 10 80 0 110 0 |
6 85 90 95 100 105 |
Sample Input 2 | Sample Output 2 |
---|---|
24 3 10 10 30 10 20 20 |
4 17.071067 20 22.928932 |
Sample Input 3 | Sample Output 3 |
---|---|
1280 10 100 120 97 50 94 99 74 97 50 87 29 71 13 50 3 26 0 0 100 0 |
6 27.5015466 44.3204382 59.0041321 72.7008423 85.8494453 |