湖州住房建设部网站,西安公司章程在哪里下载,WordPress文章无法打开,仁怀网站建设不好出手标题#xff1a;油漆面积
X星球的一批考古机器人正在一片废墟上考古。 该区域的地面坚硬如石、平整如镜。 管理人员为方便#xff0c;建立了标准的直角坐标系。 每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。
经过各种测量#xff0c;每个机器人都会报告…标题油漆面积
X星球的一批考古机器人正在一片废墟上考古。 该区域的地面坚硬如石、平整如镜。 管理人员为方便建立了标准的直角坐标系。 每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。
经过各种测量每个机器人都会报告一个或多个矩形区域作为优先考古的区域。 矩形的表示格式为(x1,y1,x2,y2)代表矩形的两个对角点坐标。 为了醒目总部要求对所有机器人选中的矩形区域涂黄色油漆。 小明并不需要当油漆工只是他需要计算一下一共要耗费多少油漆。 其实这也不难只要算出所有矩形覆盖的区域一共有多大面积就可以了。 注意各个矩形间可能重叠。
本题的输入为若干矩形要求输出其覆盖的总面积。
输入格式 第一行一个整数n表示有多少个矩形(1n10000) 接下来的n行每行有4个整数x1 y1 x2 y2空格分开表示矩形的两个对角顶点坐标。 (0 x1,y1,x2,y2 10000) 输出格式 一行一个整数表示矩形覆盖的总面积。
例如 输入 3 1 5 10 10 3 1 20 20 2 7 15 17
程序应该输出 340
再例如 输入 3 5 2 10 6 2 7 12 10 8 1 15 15 程序应该输出 128
资源约定 峰值内存消耗含虚拟机 256M CPU消耗 2000ms 请严格按要求输出不要画蛇添足地打印类似“请您输入…” 的多余内容。 所有代码放在同一个源文件中调试通过后拷贝提交该源码。 不要使用package语句。不要使用jdk1.7及以上版本的特性。 主类的名字必须是Main否则按无效代码处理。
解析由题意“矩形长和宽不超过10000”也就是说所有矩形加起来去除叠加部分面积不会超过10000*10000。由于是当练习题做所以我直接定义了一个int类型的二维数组int[10005][10005]测试结果全部是内存溢出。后来看了别人的博客才明白为什么当然他的博客也做了部分优化有兴趣的朋友可以去评论区找找。 解题的思路是没有问题的内存溢出在于一个int变量占4个字节所定义的这个数组内存占到4*10^8 B约等于400MB超出题目要求的256M。其实每个“点”只有涂和不涂两种状态所以数组只要定义为boolean就可以了一个boolean变量只占1个字节这样一来数组占的内存就最多只有100M。
import java.util.Scanner;public class Main {static int n, sum 0;static int[][] p new int[10005][10005];public static void main(String[] args) {Scanner in new Scanner(System.in);n in.nextInt();for (int i 0; i n; i) {int x1 in.nextInt();int y1 in.nextInt();int x2 in.nextInt();int y2 in.nextInt();paint(x1, y1, x2, y2);}for (int i 0; i p.length; i) {for (int j 0; j p[i].length; j) {sum p[i][j];}}System.out.println(sum);}private static void paint(int x1, int y1, int x2, int y2) {// TODO Auto-generated method stubfor (int i x1; i x2; i) {for (int j y1; j y2; j) {p[i][j] 1;}}}
}
这道理放到蓝桥杯的系统上进行了测试可以通过5个测试点一共6个。 第一个测试点如下
20
29 48 93 107
59 62 87 97
87 94 84 94
35 49 5 18
96 107 57 58
95 98 42 44
46 55 44 51
71 75 63 80
13 24 27 43
61 69 44 51
39 40 46 47
41 48 99 115
55 63 28 37
94 105 97 112
40 52 91 94
93 106 45 49
36 54 35 36
39 52 81 92
44 47 14 26
75 89 5 8
测试数据输出为3796其中最大的面积已经是(99-41)*(115-48)3886所以测试结果时有问题的。实际结果应该为4909。
