O-Ring
Bytelend has N towns. Every town is determined with x and y coordinates. Byteland has one old radio transmitter as well. Only one type of sending signals remain in function and this is covering ring shaped part of land width D with center in transmitter. Since price is higher if width of ring is bigger you need to determined minimum possible width of ring but also cover at least K towns.
InputIn first line of input are two integers N and K and two more integers Xo and Yo position of transmitter. (1 <= K <= N <= 5000) i (-2000<=Xi,Yi<=2000)
In next N lines are two integer in each line. Xi and Yi coordinate if i-th town. (-2000<=Xi,Yi<=2000).
In next N lines are two integer in each line. Xi and Yi coordinate if i-th town. (-2000<=Xi,Yi<=2000).
OutputIn first line of output print minimum width of ring D on two decimal places, which cover at least K towns. If multiple solution exist, print one with smaller area.
In second line of output print number of towns which can catch radio signal.
If enough towns have same distance from transmitter, we will consider that ring is wide 0.00.
Transmitter can be placed in some of towns as well as out of towns..
In second line of output print number of towns which can catch radio signal.
If enough towns have same distance from transmitter, we will consider that ring is wide 0.00.
Transmitter can be placed in some of towns as well as out of towns..
Input:
5 3 2 2
5 0
4 2
4 3
3 3
2 3
Output:
0.82
3
Input:
2 1 0 0
-1 -1
1 1
Output:
0.00
2
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.