1043: Atlantis
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|
 | 3s | 8192K | 431 | 155 | Standard |
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 containsfour 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 “Testcase #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
注意到要表示一个矩形，只需要知道其2个顶点的坐标就可以了(最左下，最右上)。可以用2个数组x[0...2n-1]，y[0...2n-1]记录下矩形Ri的2个坐标(x1,y1)，(x2,y2)，然后将数组x[0...xn-1]，y[0...2n-1]排序，为下一步的扫描线作准备，这就是离散化的思想。这题还可以用线段树做进一步优化，但是这里只介绍离散化的思想。
看下面这个例子：有2个矩形(1,1)，(3,3)和(2,2)，(4,4)。如图：
图中虚线表示扫描线，下一步工作只需要将这2个矩形覆盖过的部分的bool数组的对应位置更新为true，接下去用扫描线从左到右，从上到下扫描一遍，就可以求出矩形覆盖的总面积。
这个图对应的bool数组的值如下：
1 1 0 1 2 3
1 1 1 <----> 4 5 6
0 1 1 7 8 9#include<stdio.h>
#include<iostream>
#include<algorithm>
#define MAXN 201
using namespace std;
struct Node
{
int l, r;//线段树的左右整点
int c;//c用来记录重叠情况
double cnt, lf, rf;//
//cnt用来计算实在的长度，rf,lf分别是对应的左右真实的浮点数端点
} segTree[MAXN * 3];
struct Line
{
double x, y1, y2;
int f;
} line[MAXN];
//把一段段平行于y轴的线段表示成数组 ，
//x是线段的x坐标，y1,y2线段对应的下端点和上端点的坐标
//一个矩形 ，左边的那条边f为1，右边的为-1，
//用来记录重叠情况，可以根据这个来计算，nod节点中的c
bool cmp(Line a,Line b)//sort排序的函数
{
return a.x < b.x;
}
double y[MAXN];//记录y坐标的数组
void Build(int t,int l,int r)//构造线段树
{
segTree[t].l = l;
segTree[t].r = r;
segTree[t].cnt = segTree[t].c = 0;
segTree[t].lf = y[l];
segTree[t].rf = y[r];
if (l + 1 == r) return;
int mid = (l + r) >> 1;
Build(t << 1, l, mid);
Build(t << 1 | 1, mid, r);//递归构造
}
void calen(int t)//计算长度
{
if (segTree[t].c > 0)
{
segTree[t].cnt = segTree[t].rf - segTree[t].lf;
return;
}
if (segTree[t].l + 1 == segTree[t].r)
segTree[t].cnt = 0;
else
segTree[t].cnt = segTree[t << 1].cnt + segTree[t << 1 | 1].cnt;
}
void update(int t, Line e)//加入线段e，后更新线段树
{
if (e.y1 == segTree[t].lf && e.y2 == segTree[t].rf)
{
segTree[t].c += e.f;
calen(t);
return;
}
if (e.y2 <= segTree[t << 1].rf)
update(t << 1, e);
else
if(e.y1 >= segTree[t << 1 | 1].lf)
update(t << 1 | 1, e);
else
{
Line tmp = e;
tmp.y2 = segTree[t << 1].rf;
update(t << 1, tmp);
tmp = e;
tmp.y1 = segTree[t << 1 | 1].lf;
update(t << 1 | 1, tmp);
}
calen(t);
}
int main()
{
int i, n, t, iCase = 0;
double x1, y1, x2, y2;
while(scanf("%d", &n) && n)
{
iCase++;
t = 1;
for(i = 1; i <= n; i++)
{
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
line[t].x = x1;
line[t].y1 = y1;
line[t].y2 = y2;
line[t].f = 1;
y[t] = y1;
t++;
line[t].x = x2;
line[t].y1 = y1;
line[t].y2 = y2;
line[t].f = -1;
y[t] = y2;
t++;
}
sort(line + 1, line + t, cmp);
sort(y + 1, y + t);
Build(1, 1, t - 1);
update(1, line[1]);
double res = 0;
for(i = 2; i < t; i++)
{
res += segTree[1].cnt * (line[i].x - line[i - 1].x);
update(1, line[i]);
}
printf("Test case #%d\n", iCase);
printf("Total explored area: %.2lf\n\n", res);
}
return 0;
}
posted on 2011-10-25 23:52
LLawliet 阅读(244)
评论(0) 编辑 收藏 引用 所属分类:
线段树