2 shunfurh shunfurh 于 2017.09.02 10:08 提问

Atlantis

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.

Input

The input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.

The input file is terminated by a line containing a single 0. Don��t process it1.

Output

For each test case, your program should output one section. The first line of each section must be ��Test case #k��, where k is the number of the test case (starting with 1). The second one must be ��Total explored area: a��, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.

Output a blank line after each test case.

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.17 00:25
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
POJ 1542 Atlantis(线段树 面积并+离散化)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1542 Problem Description There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even incl
HDU-1542-Atlantis-线段树+面积并(模板)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1542 看了很短网上的博客,都写得很不错,我就是学着这篇博客写的,链接:http://www.cnblogs.com/ka200812/archive/2011/11/13/2247064.html 但是我觉得他们写的都不太详细,缺少步骤,像我这种菜鸟,就花了一上午,才搞定这一题; 对于新学,我觉
HDU 1542 Atlantis (线段树 + 扫描线 + 离散化)
Atlantis Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8998    Accepted Submission(s): 3856 Problem Description There are several
HDU1542Atlantis(扫描线)
HDU1542Atlantis(扫描线) 题目链接 题目大意:给你n个覆盖矩形,问最后覆盖的面积。 解题思路:将每个矩形拆成两条线段,一条是+1的,另一条是减1的,然后扫描先从上往下扫描,碰到加1的那条线段,那么这条线段范围内的节点的覆盖信息就+1,直到碰到减1这个线段范围内的节点的覆盖信息都需要减1。这样说可能理解不了,就可以画画矩形然后画下扫描线在理解理解。然后就是需要离散化
POJ 1151 Atlantis(重叠矩阵面积和=离散化)
POJ 1151 Atlantis(重叠矩阵面积和=离散化) http://poj.org/problem?id=1151 题意:        给你n个边平行于坐标轴的矩阵(任意两个矩阵可能重叠),让要你求这些矩阵的总面积.(注意x1且y1) 分析:        本题可以用线段树扫描线做,不过终归还是用离散化的思想来做,下面直接离散化做.(未使用线段树)        假设输入的矩
POJ1151Atlantis【离散化+扫描线+线段树】
Language: Default Atlantis Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 19315   Accepted: 7335 Description There are several ancient Greek texts that
hdu1542 Atlantis (线段树+扫描线+离散化)
Atlantis Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9032    Accepted Submission(s): 3873 Problem Description There are several
HDU 1542 Atlantis(线段树:扫描线)
HDU1542 Atlantis(线段树:扫描线) 题意: 二维平面有n个平行于坐标轴的矩形,现在要求出这些矩形的总面积. 重叠部分只能算一次. 分析:        首先假设有下图两个矩阵,我们如果用扫描线的方法如何计算它们的总面积呢? 首先我们将矩形的上下边分为上位边(即y坐标大的那条平行于x轴的边),和下位边(y坐标小的平行于x轴的边).然后我们把所有矩形的上下位边按照他们y坐标
Atlantis(P1151)
先用好像不是线段树的方法模仿做出,,然后再做一下线段做的方法吧 #include #include #include #include #include #include #include #include using namespace std; #define N 333 struct my { int i; double num; bool operator<(my
poj1151-- Atlantis(线段树+离散化+扫描线)
Atlantis Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u Submit Status   Description There are several ancient Greek texts that contain descriptions of