printРабочее место участника

printЗадачи

1425. Fish Catch

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Fishermen of New England like to catch so called "SLSS" fish. SLSS stands for "straight line same speed fish", because such fish is very lazy and rarely changes its speed and direction of travel. Fishermen bring a net in a shape of a circle, that has an adjustable radius. They locate the best position for the center of the net, based on their visual observation of high concentration of fish. There are `N` fish. They also write down the initial position and the direction of travel of each fish. Their plan is to catch `K` fish in order to make a nice dinner for their families. However, they don not want to catch many more fish, so that there is enough fish left in the Ocean. They need to set a proper radius length of the net, which leads them to a hard computational problem. As a fishermen's friend, please help them to find the smallest radius of the net such that there is a moment when they can dip the net into the Ocean and catch at least `K` fish.
Input
The first line of the input contains two integers `C_x` and `C_y` separated by a space character (`1\ ≤\ C_x,C_y\ ≤\ 10^4`), that represent the coordinates of the center of the net. The second line of the input contains two integers `N` and `K` separated by a space character (`5\ ≤\ N\ ≤\ 1000`, `1\ ≤\ K\ ≤\ N`). Each of the next `N` lines contain four integers `A_x,\ A_y,\ B_x,\ B_y` separated by a space character (`0\ ≤\ A_x,A_y,B_x,B_y\ ≤\ 10^4`). `A_x` and `A_y` represent the initial coordinates of a fish (at time zero), while `B_x` and `B_y` represent the estimated coordinates of a fish after 1 second. Note that fishermen can use the net at any moment starting from time zero.
Output
In the first line of the output write one real number `R` using exactly 5 decimal digits of precision – which is the desired radius of the net. It should be followed by a newline.

Sample Input

6 7
5 4
1 4 1 11
4 12 10 10
4 9 4 7
2 4 10 4
3 1 9 1

Sample Output

5.00000
Source: MIT Programming Team Contest 1, 2008
loading