HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN112 Questions 2016 > problem:


15-FE-6. 50989 - Rectangles and Points

CEN112 Questions 2016

Start: Mar.30.2016 at 03:10:22 PM
Finish: Apr.01.2016 at 05:00:00 AM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 15-FE-1. 50992 - Top K Obese Classes
• 15-FE-2. 50993 - Products in store
• 15-FE-3. 50994 - The Most Crowded...
• 15-FE-4. 50995 - Group Average
• 15-FE-6. 50989 - Rectangles an...
• 15-FE-7. 50990 - Two Neighbors
• 15-FE-8. 50991 - Intersecting Circles
• 15-HW-2. 50932 - Shifting rows and...
• 15-HW-3. 50933 - Sum of the Bigges...
• 15-HW-4. 50934 - Selling Cars
• 15-HW-5. 50935 - Max Discount
• 15-MdtE-1. 50915 - Trip to Korca
• 15-MdtE-2. 50916 - Ascending Num...

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
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).



Для отправки решений необходимо выполнить вход.

www.contester.ru