Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3414
Trail Walk

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 p1 p2 p3 ... pn, 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 CP0 and the end as CPm+1.


There 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 pi.


The first line of each case, output "Route case_number", Then m lines followed, the ith line contains "CPcase_num: (xi, yi)" where (xi, yi) represent the coordinate of the CPi. Always keep three number after the decimal point.

Sample Input

3 3
1 1
2 3
3 5

Sample Output

Route 1
CP1: (1.026, 1.051)
CP2: (1.684, 2.368)
CP3: (2.342, 3.684)

Author: WANG, Yelei
Contest: ZOJ Monthly, October 2010
Submit    Status