Fire station

A city's map can be seen as a two dimensional plane. There are N houses in the city and these houses can be seen as N points P₁ …… P_N on the two dimensional plane. For simplicity's sake, assume that the time spent from one house number to another is equal to the distance between two points corresponding to the house numbers. The government decides to build M fire stations from N houses. (If a station is build in Pi, We can think the station is next to the house and the time from the station to the house is considered zero.) It is obvious that if some place such as Pi is breaking out of fire, the nearest station will dispatched a fire engine quickly rushed to the rescue scene. The time it takes from this station to the rescue scene is called rescue time. Now you need to consider about a problem that how to choice the positions of the M fire station to minimize the max rescue time of all the houses.

The first line of the input contains one integer T, where T is the number of cases. For each case, the first line of each case contains two integers N and M separated by spaces (1 ≤ M ≤N ≤ 50), where N is the number of houses and M is the number of fire stations. Then N lines is following. The ith line contains two integers Xi and Yi (0 ≤ Xi, Yi ≤ 10000), which stands for the coordinate of the ith house.

The rescue time which makes the max rescue time is minimum.

2
4 2
1 1
1 2
2 3
2 4
4 1
1 1
1 2
2 3
2 4

1.000000
2.236068

wwr & fengzlzl

2010 Asia Regional Chengdu Site —— Online Contest