Hide

Problem B
Build a Boat

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.

Input

  • 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.

Output

  • 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

Please log in to submit a solution to this problem

Log in