Time Limit: 3 second(s) | Memory Limit: 64 MB |
As the name says, this problem is about finding the number of points in a rectangle whose sides are parallel to axis. All the points and rectangles consist of 2D Cartesian co-ordinates. A point that lies in the boundary of a rectangle is considered inside.
Initially you are given a list of points, after that you are given some queries, each query contains a rectangle. Your task is to find the number of points that lie in each of the query rectangle.
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing two integers: p, q (1 ≤ p, q ≤ 50000), where p denotes the number of points and q denotes the number of query rectangles.
Each of the next p lines contains two integers x y denoting the co-ordinate of a point. All the points are distinct.
Each of the next q lines contains four integers x_{1} y_{1} x_{2} y_{2} meaning that you are given a rectangle whose lower left co-ordinate is (x_{1}, y_{1}) and upper-right corner is (x_{2}, y_{2}). You can assume that (x_{1} < x_{2}, y_{1} < y_{2}).
You can assume that the values of the co-ordinates lie between 0 and 10^{9} (inclusive).
For each case, print the case number in a line first. Then for each query rectangle, you have to answer the number of points that lie inside that rectangle. Print each of the results in separate lines.
Sample Input |
Output for Sample Input |
1 5 6 0 0 5 9 2 3 4 6 7 7 0 0 5 9 2 2 10 11 4 6 7 9 3 3 4 5 4 6 5 7 5 7 7 9 |
Case 1: 4 4 3 0 1 2 |
Dataset is huge, use faster I/O methods.
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |