Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Question by Ibrahim Mesecan.
Rectangles and Points
Question:
You are given coordinates of n rectangles.
Then you are also given m points.
List top k rectangles which overlap with
the most number of points. If two rectangles have the
same number of overlapping points, list them
according to the order of appearance.
Note:
1) The point is count overlapping,
alsowhen it is on any edge of the rectangle.
2) The corners are random; they are not guaranteed to
be in any order.
Input specification:
In the first line, you will be given three integers:
the number of rectangles (n), the number of points (m)
and the number of top (k) rectangles to list.
The following n lines will contain 4 integers
(x1, y1, x2, y2). Then, the following m lines
will contain 2 integers (x, y) where 1 ≤ (m, n)
≤ 8,000.
Output specification:
Show k integers (order of rectangles).
Sample Input
4 6 2
4 7 7 12
5 4 8 13
3 2 7 8
4 4 12 6
5 7
6 7
1 6
10 7
2 8
3 2
|
Sample Output
3 1
|
Explanation:
There are four rectangles and 6 points given.
The first, the second and the third rectangles overlap with
two points (5, 7) and (6, 7). The third rectangle
also overlaps with (3,2). The fourth rectangle does not
overlap with any points. So, the top two rectangles are 3
(overlapping with 3 points) and 1 (overlapping with 2 points).
Для отправки решений необходимо выполнить вход.
|