2 shunfurh shunfurh 于 2017.08.27 15:20 提问

Trail Walk

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.

Input

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.

Output

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)

1个回答

devmiao
devmiao   Ds   Rxr 2017.08.27 23:52
已采纳
Csdn user default icon
上传中...
上传图片
插入图片