[Hidden]
#### 1195. E. Cut the Cake!

#### Description

On the faraway planet of Gastronomia, the native Gastronomes consider polygonal pancakes to

be the highest form of art (as well as the tastiest). Every year, they celebrate the Polycake

Festival, in which thousands of ninja chef monasteries perform the Thousand Slices, a series of

rituals of tremendous importance to Gastronome society. In each of these rituals, a polycake is

carefully placed on a ceremonial altar, and a ninja chef will solemnly cut the cake with a single,

perfectly straight slice, dividing it into two pieces, one on the North part of the altar (representing

the past) and the other on the South part (representing the future). The two pieces are carefully

separated, and their perimeters measured. The results will determine the proportions of the

ingredients used in polycakes planetwide, until the next Polycake Festival.

As the foremost Novice at the Temple of the Promised Cosmic Polycake, you are entrusted the

task of measuring the perimeters of the two slices. Take care, for any mistakes will be

mercilessly mocked by the Brotherhood of the Illusory Polycake1. It would be best if you wrote

a program to do this.

The Problem:

Given a polygon representing the polycake in the Cartesian plane and a line parallel to the X-axis

indicating the position of the slice, you are to compute the perimeter of each of the two pieces

thus formed. The perimeter of a polygon is defined as the sum of the lengths of all its sides.

Assume that the input polygons will be convex (i.e., not concave) and simple (i.e., not complex,

not intersecting).

#### Input

The first input line contains a positive integer, n, indicating the number of polycakes used in the

ritual. This is followed by n data sets, each representing a single slicing of a polycake.

The first line of each set consists of two integers, V (3 ≤ V ≤ 10) and Y (-1000 ≤ Y ≤ 1000),

representing the number of vertices in the polycake and the y-coordinate of the horizontal cut,

respectively. (Recall that the equation of a line parallel to the X-axis is of the form y=k.)

The next V lines each contain two integers, x and y (-1000 ≤ x, y ≤ 1000), the Cartesian

coordinates of the vertices of the polycake, in counter-clockwise order.

To minimize complications (and following the rules of the ritual), it is guaranteed that the cut

will always go through the cake and will never pass through a vertex.

#### Output

Then, output “a b”, the perimeters of the two slices, in increasing order. Output the results to 3

decimal places, rounded to the nearest thousandth (e.g., 77.0113 should round to 77.011, 88.0115

should round to 88.012, and 99.0117 should round to 99.012). Leave a blank line after the

output for each test case. Follow the format illustrated in Sample Output.

#### Samples

#### Source

UCF2011

be the highest form of art (as well as the tastiest). Every year, they celebrate the Polycake

Festival, in which thousands of ninja chef monasteries perform the Thousand Slices, a series of

rituals of tremendous importance to Gastronome society. In each of these rituals, a polycake is

carefully placed on a ceremonial altar, and a ninja chef will solemnly cut the cake with a single,

perfectly straight slice, dividing it into two pieces, one on the North part of the altar (representing

the past) and the other on the South part (representing the future). The two pieces are carefully

separated, and their perimeters measured. The results will determine the proportions of the

ingredients used in polycakes planetwide, until the next Polycake Festival.

As the foremost Novice at the Temple of the Promised Cosmic Polycake, you are entrusted the

task of measuring the perimeters of the two slices. Take care, for any mistakes will be

mercilessly mocked by the Brotherhood of the Illusory Polycake1. It would be best if you wrote

a program to do this.

The Problem:

Given a polygon representing the polycake in the Cartesian plane and a line parallel to the X-axis

indicating the position of the slice, you are to compute the perimeter of each of the two pieces

thus formed. The perimeter of a polygon is defined as the sum of the lengths of all its sides.

Assume that the input polygons will be convex (i.e., not concave) and simple (i.e., not complex,

not intersecting).

ritual. This is followed by n data sets, each representing a single slicing of a polycake.

The first line of each set consists of two integers, V (3 ≤ V ≤ 10) and Y (-1000 ≤ Y ≤ 1000),

representing the number of vertices in the polycake and the y-coordinate of the horizontal cut,

respectively. (Recall that the equation of a line parallel to the X-axis is of the form y=k.)

The next V lines each contain two integers, x and y (-1000 ≤ x, y ≤ 1000), the Cartesian

coordinates of the vertices of the polycake, in counter-clockwise order.

To minimize complications (and following the rules of the ritual), it is guaranteed that the cut

will always go through the cake and will never pass through a vertex.

decimal places, rounded to the nearest thousandth (e.g., 77.0113 should round to 77.011, 88.0115

should round to 88.012, and 99.0117 should round to 99.012). Leave a blank line after the

output for each test case. Follow the format illustrated in Sample Output.

Input
Copy

2 4 2 0 0 4 0 4 4 0 4 6 10 3 15 10 1 12 5 11 19 9 23 6 20

Output

Case #1: 12.000 12.000 Case #2: 25.690 35.302

Time Limit: | 1000MS (C/C++,Others×2) |

Memory Limit: | 128MB (C/C++,Others×2) |

Special Judge: | No |

AC/Submit: | 1 / 1 |

Tags: |