Fish Catch
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение 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
Source: MIT Programming Team Contest 1, 2008