
ZOJ Problem Set  3414
FatMouse is busy organizing the coming trail walk. After the route for the trail walk has been determine, the next important task is to set the location of CPs(check point). The route is composed by n line segments which only intersect on their endpoints. Set the starting point of the trail walk as origin, the coordinate of the endpoints are p_{1} p_{2} p_{3} ... p_{n}, in the order of walking direction. Now FatMouse wants to set m CPs on the route in such way that the walking distance between adjacent CPs are all equal. You can treat the starting point as the CP_{0} and the end as CP_{m+1}. InputThere are multiple test cases. The first line of each case contains two integer n, m(1 <= n, m <= 1000). Then n pairs of integer followed, giving the coordinate of p_{i}. OutputThe first line of each case, output "Route case_number", Then m lines followed, the ith line contains "CPcase_num: (x_{i}, y_{i})" where (x_{i}, y_{i}) represent the coordinate of the CP_{i}. Always keep three number after the decimal point. Sample Input3 3 1 1 2 3 3 5 Sample OutputRoute 1 CP1: (1.026, 1.051) CP2: (1.684, 2.368) CP3: (2.342, 3.684) Author: WANG, Yelei Contest: ZOJ Monthly, October 2010 