问题描述

在一个定义了直角坐标系的纸上，画一个(x1,y1)到(x2,y2)的矩形指将横坐标范围从x1到x2，纵坐标范围从y1到y2之间的区域涂上颜色。

下图给出了一个画了两个矩形的例子。第一个矩形是(1,1) 到(4, 4)，用绿色和紫色表示。第二个矩形是(2, 3)到(6, 5)，用蓝色和紫色表示。图中，一共有15个单位的面积被涂上颜色，其中紫色部分被涂了两次，但在计算面积时只计算一次。在实际的涂色过程中，所有的矩形都涂成统一的颜色，图中显示不同颜色仅为说明方便。

给出所有要画的矩形，请问总共有多少个单位的面积被涂上颜色。

输入格式

输入的第一行包含一个整数n，表示要画的矩形的个数。

接下来n行，每行4个非负整数，分别表示要画的矩形的左下角的横坐标与纵坐标，以及右上角的横坐标与纵坐标。

输出格式

输出一个整数，表示有多少个单位的面积被涂上颜色。

样例输入

2
1 1 4 4
2 3 6 5

样例输出

评测用例规模与约定

1<=n<=100，0<=横坐标、纵坐标<=100。

编程语言：Python

解题思想：

1.因为题目限定x和y都在0-100的范围内，在每次输入的时候就对矩形内的元素进行染色。

2.最后在10000个元素中进行遍历，找到染色的元素则面积增加。

3.进一步优化可以定义MaxX和MaxY来限定遍历的边界，缩小遍历的空间。

时间复杂度：O(n^3)

IDE代码如下：

N = int(input())  # 输入矩形的个数
Value = [['White' for i in range(101)] for i in range(101)]  # 特别需要注意创建二维数组的方法
for i in range(N):
    X1, Y1, X2, Y2 = map(int, input().split())  # 一行输入矩形四个坐标的值
    for x in range(X1, X2):  # 遍历矩形的X坐标
        for y in range(Y1, Y2):  # 遍历矩形的Y坐标
            Value[x][y] = 'Blue'  # 将矩形内的元素染色
 
Area = 0  # 面积
for i in range(101):  # 遍历完整范围内的Y坐标
    for j in range(101):  # 遍历完整范围内的X坐标
        if Value[i][j] == 'Blue':  # 如果这个坐标被染色
            Area += 1
print(Area)

< >

评论板

共有 4 条评论

Jorcift

cialis generic best price A new CT scan was obtained after 3 mo, which demonstrated residual rectal tumour with stricture and proximal fecal loading unchanged, and liver metastases, not significantly changed

2023-04-30 19:59 回复
intuido

The median urine volume on the next day of treatment was 1595 120 6630 mL and the body weight change was 1 buy cialis without prescription In acute intestinal amebiasis, Doxicen and Doxicen CAP may be a useful adjunct to amebicides

2023-06-04 13:49 回复
intuido

i have atrial fibrillation can i use viagra Following oral dosing, ribociclib was rapidly absorbed with median Tmax ranging from 1 to 5 hours

2023-06-10 16:35 回复
DwIiTh

Much of the lag is down to shoppers reluctanceto buy clothes they can t try on buy cialis with paypal

2023-07-15 16:21 回复

CCF-CSP_20140902:画图