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
注意到要表示一個(gè)矩形，只需要知道其2個(gè)頂點(diǎn)的坐標(biāo)就可以了(最左下，最右上)。可以用2個(gè)數(shù)組x[0...2n-1]，y[0...2n-1]記錄下矩形Ri的2個(gè)坐標(biāo)(x1,y1)，(x2,y2)，然后將數(shù)組x[0...xn-1]，y[0...2n-1]排序，為下一步的掃描線作準(zhǔn)備，這就是離散化的思想。這題還可以用線段樹做進(jìn)一步優(yōu)化，但是這里只介紹離散化的思想。
看下面這個(gè)例子：有2個(gè)矩形(1,1)，(3,3)和(2,2)，(4,4)。如圖：
圖中虛線表示掃描線，下一步工作只需要將這2個(gè)矩形覆蓋過的部分的bool數(shù)組的對(duì)應(yīng)位置更新為true，接下去用掃描線從左到右，從上到下掃描一遍，就可以求出矩形覆蓋的總面積。
這個(gè)圖對(duì)應(yīng)的bool數(shù)組的值如下：
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;//線段樹的左右整點(diǎn)
int c;//c用來記錄重疊情況
double cnt, lf, rf;//
//cnt用來計(jì)算實(shí)在的長(zhǎng)度，rf,lf分別是對(duì)應(yīng)的左右真實(shí)的浮點(diǎn)數(shù)端點(diǎn)
} segTree[MAXN * 3];
struct Line
{
double x, y1, y2;
int f;
} line[MAXN];
//把一段段平行于y軸的線段表示成數(shù)組 ，
//x是線段的x坐標(biāo)，y1,y2線段對(duì)應(yīng)的下端點(diǎn)和上端點(diǎn)的坐標(biāo)
//一個(gè)矩形 ，左邊的那條邊f(xié)為1，右邊的為-1，
//用來記錄重疊情況，可以根據(jù)這個(gè)來計(jì)算，nod節(jié)點(diǎn)中的c
bool cmp(Line a,Line b)//sort排序的函數(shù)
{
return a.x < b.x;
}
double y[MAXN];//記錄y坐標(biāo)的數(shù)組
void Build(int t,int l,int r)//構(gòu)造線段樹
{
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);//遞歸構(gòu)造
}
void calen(int t)//計(jì)算長(zhǎng)度
{
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 閱讀(257)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
線段樹