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
© 2015 HUST ACMICPC TEAM. All Right Reserved.