CatchTheMice
SRM 426 · 2008-11-22 · by StevieT
Problem Statement
A fairground operator has designed a new game, called "Catch the Mice". This consists of a set of electronic "mice" that move around on a large board. The contestant controls a square cage, which is initially suspended above the board. The contestant can position the cage anywhere above the board and then drop it, the aim being to enclose some of the mice in the cage. The contestant wins a prize accoring to how many mice he managed to capture. If the contestant captures all of the mice, then he wins the grand prize, which is a sports car. However the fairground operator is not entirely honest, and wants your help to rig the game so that it is impossible to win the grand prize. He wants to make the cage sufficiently small that at no point in time are the mice close enough for it to capture them all.
Consider the mice as a set of points moving in an infinite 2D cartesian plane. Each mouse starts at a known position at time t = 0, then moves with constant velocity in time t ⥠0. Consider the cage as a perfect square of side length L, that can be positioned anywhere in the plane with its sides parallel to the axes (i.e., the contestant can move, but cannot rotate the cage). The cage can be dropped at any time t ⥠0 and it will capture a mouse if at that point in time the mouse's position is strictly contained within its boundary (mice exactly on the boundary are not considered to be captured). You should calculate the maximum value of L that doesn't allow all the mice to be captured.
You will be given 4
Notes
- Your return value must be accurate to an absolute or relative tolerance of 1e-9.
Constraints
- xp, yp, xv and yv will contain between 2 and 50 elements, inclusive.
- xp, yp, xv and yv will contain the same number of elements.
- Each element of xp, yp, xv and yv will be between -1000 and 1000, inclusive.
- At no point in time t ⥠0 will any two mice occupy the same point in space.
{0,10}
{0,10}
{10,-10}
{0,0}
Returns: 10.0
A cage with side length greater than 10 would be able to catch both the mice at any time before t = 1.
{0,10,0}
{0,0,10}
{1,-6,4}
{4,5,-4}
Returns: 3.0
At time t = 1, the mice are at positions (1, 4), (4, 5) and (4, 6). At this point in time any cage with an edge length larger than 3 would be able to catch them. This is the point in time when the mice are closest together.
{50,10,30,15}
{-10,30,20,40}
{-5,-10,-15,-5}
{40,-10,-1,-50}
Returns: 40.526315789473685
{0,10,10,0}
{0,0,10,10}
{1,0,-1,0}
{0,1,0,-1}
Returns: 10.0
{13,50,100,40,-100}
{20,20,-150,-40,63}
{4,50,41,-41,-79}
{1,1,1,3,-1}
Returns: 212.78688524590163
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CatchTheMice with a public method double largestCage(vector<int> xp, vector<int> yp, vector<int> xv, vector<int> yv) · 128 test cases · 2 s / 256 MB per case