给出所有要画的矩形,请问总共有多少个单位的面积被涂上颜色。 输入格式 输入的第一行包含一个整数n,表示要画的矩形的个数。 接下来n行,每行4个非负整数,分别表示要画的矩形的左下角的横坐标与纵坐标,以及右上角的横坐标与纵坐标。 输出格式 输出一个整数,表示有多少个单位的面积被涂上颜色。 样例输入 2 1 1 4 4 2 3 6 5 样例输出 15 java代码展示
时间: 2024-03-23 14:41:49 浏览: 17
以下是Java代码实现:
```
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] board = new int[101][101]; // 定义一个二维数组,表示二维坐标系
int count = 0; // 记录涂上颜色的单位面积
for (int i = 0; i < n; i++) {
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
// 将矩形在数组中对应的位置的值加1
for (int j = x1 + 1; j <= x2; j++) {
for (int k = y1 + 1; k <= y2; k++) {
if (board[j][k] == 0) {
count++;
}
board[j][k]++;
}
}
}
// 统计值为2或以上的位置的个数,并将它们的值减去1
int overlap = 0;
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++) {
if (board[i][j] >= 2) {
overlap++;
count--;
board[i][j]--;
}
}
}
// 统计数组中所有非零元素的个数
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++) {
if (board[i][j] != 0) {
count++;
}
}
}
System.out.println(count);
}
}
```
时间复杂度为O(n^2),空间复杂度为O(1)。