牛牛数星星

发表于 | 分类于

题目

一闪一闪亮晶晶，满天都是小星星，牛牛晚上闲来无聊，便躺在床上数星星。
牛牛把星星图看成一个平面，左上角为原点(坐标为(1, 1))。现在有n颗星星，他给每颗星星都标上坐标(xi，yi)，表示这颗星星在第x行，第y列。
现在，牛牛想问你m个问题，给你两个点的坐标(a1, b1)(a2，b2)，表示一个矩形的左下角的点坐标和右上角的点坐标，请问在这个矩形内有多少颗星星（边界上的点也算是矩形内）。

输入

星星数

星星坐标(a1,b1)

……

问题数

问题坐标a1,b1,a2,b2

……

思路

输入完所有星星后，遍历整个空间，计算每个点的左下角有多少个星星。在计算矩形面积时，数量为右上角-左上角-右下角+左下角的左下点（减的时候多减了一个左下角）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
snum = int(raw_input())
star = [[0 for col in range(1001)] for row in range(1001)]
for i in xrange(snum):
    line = raw_input().strip()
    x = int(line.split(' ')[0])
    y = int(line.split(' ')[1])
    star[x][y] +=1
num = [[0 for col in range(1001)] for row in range(1001)]
#用动态规划计算每个点的左下角的星星数量
for i in xrange(1,1001):
    for j in xrange(1,1001):
        num[i][j] = num[i-1][j] + num[i][j-1] + star[i][j] - num[i-1][j-1]


qnum = int(raw_input())
# juxinglist = []
for i in xrange(qnum):
    n = 0
    line = raw_input().strip()
    a1 = int(line.split(' ')[0])
    b1 = int(line.split(' ')[1])
    a2 = int(line.split(' ')[2])
    b2 = int(line.split(' ')[3])
    #计算矩形内的星星数量
    print num[a2][b2] - num[a1-1][b2] - num[a2][b1-1]  + num[a1-1][b1-1]