Codah ClubTrain. Submit. Improve.
Sign in
English
#0000A4

z-radar

Mister Little Z. wants to design a radar that will detect any internet activity. We assume that the internet activity goes through some cables. We say that the cables are straight line-segments in a plane.


Mister Little Z. knows where he wants to position the radar, but he doesn't know how strong the radar should be. By how strong, we mean at what distance can it detect activity in a cable. If the radar has power D then it can detect internet activity in any cable which that is at distance less or equal D (there is a point on the cable that is less than D units of distance apart from the position of the radar).


Mister Little Z. released that is too hard to make a radar that will detect activity in all the cables, so he wants to make a radar that will detect activity in at least K different cables (no matter which ones). Since it is cheaper to make less powerful radars, he wants to find a minimum D such that the radar can detect activity in at least K different cables. In other words, there are at least K cables that have some point that is at distance at most D from the position of the radar.


Your job is to help Little Z find out what is the minimal power D that the radar can have so that it can detect activity in at least K different cables


InputThe input is read from the standard input. From the first line read two integers X0 and Y0, both in the interval [-10000,10000], that represent the position coordinates of the position of the radar. From the second line read two integers N and K, (1 <= K <= N <= 50000). N is the number of cables, and K is the minimal number of cables that the radar should be able to detect. From each of the next N lines read four integers X1, Y1, X2, Y2, all in the interval [-10000, 10000], that represent the starting and ending coordinates of the cable.

OutputTo one line of the standard output write one real number with two decimal places precision that represents minimal power of the radar D (the distance at which the radar can detect activity) so that it can detect activity in at least K different cables


Input:
0 0
4 2
1 1 2 1
2 2 3 2
0 3 1 3
0 4 1 4

Output:
2.83

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.