John is flying to Las Vegas for the TopCoder finals. The flight is several hours long, and he can't sleep, so he decides to play his favorite mobile phone game. The game is played on a n x n 2-dimensional plane, where (0, 0) is the lower-left corner. There is a single monster at each point with integer coordinates except at (0, 0). At (0, 0), there's a laser gun that John can use to kill monsters. He can take at most k shots. On each shot, he can aim the gun in any direction and press a button that releases an infinite laser ray that kills all monsters in its path. The monsters are quite small so we can treat them as points.
Some monsters were so afraid of John that they decided to escape before the game starts, and they are now missing from the battlefield. You are given ints n and k, and a String[] missing. Concatenate the elements of missing to obtain a comma separated list of the points where monsters are missing. Each point is formatted as "row column" (quotes for clarity), where rows are numbered from bottom to top starting at 0 and columns are numbered from left to right starting at 0. Return the maximum number of monsters that John can kill using no more than k shots.
|