用算法来实现平面上矩形交叉的一个算法的问题怎么解决,用C语言怎么编写代码实现

Problem Description

The ACM Student Chapter has just been given custody of a number of school bulletin boards. Several members agreed to clear off the old posters. They found posters plastered many levels deep. They made a bet about how much area was left clear, what was the greatest depth of posters on top of each other, and how much of the area was covered to this greatest depth. To determine each bet's winner, they made very accurate measurements of all the poster positions as they removed them. Because of the large number of posters, they now need a program to do the calculations. That is your job.
A simple illustration is shown above: a bulletin board 45 units wide by 40 high, with three posters, one with corners at coordinates (10, 10) and (35, 20), another with corners at (20, 25) and (40, 35), and the last with
corners at (25, 5) and (30, 30). The total area not covered by any poster is 1300. The maximum number of posters on top of each other is 2. The total area covered by exactly 2 posters is 75.

Input
The input will consist of one to twenty data sets, followed by a line containing only 0. On each line the data will consist of blank separated nonnegative integers.
The first line of a dataset contains integers n w h, where n is the number of posters on the bulletin board, w and h are the width and height of the bulletin board. Constraints are 0 < n <= 100; 0 < w <= 50000; 0 < h <= 40000.
The dataset ends with n lines, each describing the location of one poster. Each poster is rectangular and has horizontal and vertical sides. The x and y coordinates are measured from one corner of the bulletin board. Each line contains four numbers xl yl xh and yh, where xl and yl, are the lowest values of the x and y coordinates in one corner of the poster and xh and yh are the highest values in the diagonally opposite corner.Each poster fits on the bulletin board, so 0 2 xl < xh 2 w, and 0 2 yl < yh 2 h.

Output
There is one line of output for each data set containing three integers, the total area of the bulletin board that is not covered by any poster, the maximum depth of posters on top of each other, and the total area covered this maximum number of times.
Caution: An approach examining every pair of integer coordinates might need to deal with 2 billion coordinate pairs.

Sample Input
3 45 40
10 10 35 20
20 25 40 35
25 5 30 30
1 20 30
5 5 15 25
2 2000 1000
0 0 1000 1000
1000 0 2000 1000
3 10 10
0 0 10 10
0 0 10 10
0 0 10 10
0

Sample Output
1300 2 75
400 1 200
0 1 2000000
0 3 100

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

2
使用遗传算法进行的自动排课设计,需要指出算法具体对应的代码中
4
javascript如何用数组实现冒泡排序的算法,不用sort函数怎么实现?
5
关于计算机视觉模板匹配问题的算法解决思路
2
使用Python实现K均值聚类算法使用什么变成思想
1
Android 定位坐标过滤算法实现
3
给出一个时间复杂度为O(n的立方根)的求立方根的算法并解释算法原理
1
关于向量置乱算法与rand()的一种实现之间的问题,请看图
1
Nurbs曲面的裁剪算法问题
2
数据结构方面的一个问题算法怎么实现?
1
使用SDFT算法实现对谐波信号提取
0
如何用DSP实现遗传算法?
0
Redis去重算法Bloom Filter算法的通用工具类(java实现),有木有
1
数据结构上的一个线性表的冲突的解决,是不是用哈希算法怎么采用C语言的实现方式
0
单调栈实现连续矩形最大面积的算法,报错如上,求大神指点
0
数据结构对于棋盘的一个分割子的算法的问题,运用C语言技术的编程实现
1
俄罗斯方块是否能在矩形中填充的一个算法问题,怎么用C语言编程解决的
0
寻找存在的区间的整数的算法问题,怎么利用C语言程序的算法来实现的
0
链表解决这里的路径的一个遍历的算法问题的做法怎么实现,用C语言的程序设计语言
0
一个矩形构成的矩阵的算法问题,如何利用C程序的设计的语言的方式实现呢
0
平面上的点构成的路径的搜索的一个算法,怎么利用C语言的程序的设计的办法来实现的