13521번 - 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.

• One line containing an integer C (10 ≤ C ≤ 10⁹), the minimum area of a bulkhead section.
• One line containing an integer N (3 ≤ N ≤ 10⁵), the number of vertices in the artists’ design for the boat.
• N lines, each containing two positive integers: x and y (−10⁴ ≤ x, y ≤ 10⁴), 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.

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⁻⁶