11431번 - Mr. Gorbachev, Tear Down This Wall! 다국어

One of the iconic moments of the reunification between Eastern and Western Germany was when the wall separating East and West Berlin was torn down. Pieces of brick from the wall are now part of many museums and private collections.¹ Famously, in 1987, President Reagan had asked the Soviet Union to allow East Germany to open up to the West with the now-famous phrase “Mr. Gorbachev, Tear Down This Wall!” Of course, it would have taken Mr. Gorbachev himself quite a while to do so, since the wall was quite long and sturdy. So he’d likely have asked a few buddies to help. Here, you are to compute how long it would have taken them together to tear down the Berlin wall.

You will be given a description of the wall as a sequence of points in a 2-D coordinate system; all coordinates will be integers, and we will make sure that all wall pieces are either horizontal or vertical, but never at an angle. You will also be told how much wall (length) per hour one person can tear down, and how many people there are. From this, you are to compute the necessary time to tear down the wall.

¹As are, most likely, random pieces of brick sold for a fortune to tourists who were not able to tell whether a particular piece had been previously in the wall.

The first line is the number K of input data sets, followed by the K data sets, each of the following form:

The first line of the data set contains three integers n, s, p. The integer 1 ≤ n ≤ 1000 is the number of straight-line segments in the wall. 0 < s < 100 is the number of hours it takes one person to tear down one meter of wall. 1 ≤ p ≤ 1000 is the number of people tearing down the wall.

This is followed by n + 1 lines, each containing two integers x_i, y_i with −10000 ≤ x_i, y_i ≤ 10000. This is the i th point describing the wall. The i th segment of the wall runs from (x_i, y_i) to (x_i+1, y_i+1). As promised above, all wall pieces are horizontal or vertical, meaning that for each i, either x_i+1 = x_i or y_i+1 = y_i. Furthermore, we will ensure that the wall never crosses itself.

For each data set, output “Data Set x:” on a line by itself, where x is its number.

Then output the number of hours it will take the p people to tear down the entire wall, rounded up to the nearest integer. (So if it would take 3.1 hours, you should output 4, not 3.)

Each data set should be followed by a blank line.