1573 - Grid Computing
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 21
Solved: 9
- Description
- John has recently joined the grid computing lab, and he got his first assignment, compute the total value in the grid. There are R*C grid points on the plane, every grid point has an active value. John was given a polygon to compute the total active value in that polygon, total active value in a polygon is the sum of all grids’ active value which inside or on the boundary of polygon. as you know, each grid computing network has an processing center, so do the john’s polygon, a processing center is a grid point which is inside the polygon(not on the boundary), and through it the whole grid computing can be launched. (But actually it doesn’t matter whether you know the processing center, we provide it just for the completeness of problem)
- Input
- The first line of the input file contains integer number T - the number of test cases. For each test case, the first line contains two integer numbers R C. The next R lines contain C integers each, giving the active value of grid point respectively. then followed by one integer N indicates the polygon’s points number, the next N lines has two integer numbers X Y each denotes point’s coordinates (X means the X-th row of R*C grids, Y means the Y-th column of R*C grids). the last line has two integer number X Y which means the coordinates of the processing center.
(1 <= R, C <= 1000)
(1 <= N <= 20000)
(0<=X<R, 0<=Y <C)
- Output
- Only one line formatted as:
Case #X: Y
Where X is the test case number, starting from 1, and Y is the total active value of the given polygon.
- sample input
-
2 3 3 1 1 1 1 1 1 1 1 1 4 0 0 2 0 2 2 0 2 1 1 4 6 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 9 2 1 2 3 3 4 2 5 1 5 1 4 0 4 1 3 1 2 2 4
- sample output
-
Case #1: 9 Case #2: 11
- hint
- This picture may be helpful to you.
- source
- Jian HE