本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[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

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

Source

UCF2011
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1023. UCF 2011
My history solutions

You didn't submit any solution!
Submit your solution

Login Register