Cat and Mouse
All submissions for this problem are available.
N cats and N mice are situated in a 2-D plane. Mota Chuha wants to choose K number of animals in such a way that the distance between any pair of chosen cat and chosen mouse is minimized. Distance between the same type of chosen animals doesn't matter. In other words, suppose Chota Chuha chooses cats C1,C2,C3,.....Cm and mice M1,M2,M3,.....Mn, then maximum of Distance(Ci,Mj) should be minimized.
The first line of the input contains pair of integers N and K.
Next N lines will contain a pair of integers denoting the co-ordinates of the cats.
Next N lines will contain a pair of integers denoting the co-ordinates of the mice.
Output the minimized distance. The output value must have an absolute or relative error smaller than 1e-6.
- 1 ≤ N ≤ 200
- (N+1) ≤ K ≤ 2*N
- 0 ≤ X or Y-coordinates ≤ 105
- No two animals are at the same position
3 4 1 0 2 0 3 0 1 1 2 1 3 1
Does't matter how you choose, A pair of cat and mouse will be at distance of square root of 2.
|Tags||acm15amr, amitpandeykgp, binary-search, matching|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.