題目鏈接：poj1151 hdu1542
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHByZSBjbGFzcz0="brush:java;">/*hdu 1542 Atlantis/poj 1151 Atlantis
題意：求矩形面積並
思路：將x離散化後建樹(以區間建樹)，將矩形分為上下兩邊，
上邊為入邊，下邊為出邊，從下往上掃描
注意建樹使用區間建樹，即線段樹的節點表示的是線段，而非端點
PS：掃描線，黑書412頁
*/
#include
#include
#include
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 200;
int cnt[N<<2];//表示該區間入邊比出邊多幾個，有入必有出，
double sum[N<<2];//代表該區間內被覆蓋的線段的長度總和
double x[N<<1];
struct seg
{
double l, r, h;
int s;
seg(){}
seg(double a, double b, double c, int d):l(a), r(b), h(c), s(d){}
bool operator < (const seg &cmp)const
{
return h < cmp.h;
}
}ss[N];
void pushup(int l, int r, int rt)
{
if(cnt[rt]) sum[rt] = x[r+1] - x[l];
else if(l == r) sum[rt] = 0;
else sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void update(int L, int R, int c, int l, int r, int rt)
{
if(L <= l && r <= R)
{
cnt[rt] += c;
pushup(l, r, rt);
return;
}
int m = (l+r) >> 1;
if(L <= m) update(L, R, c, lson);
if(m < R) update(L, R, c, rson);
pushup(l, r, rt);
}
int main()
{
int n,p = 1;
while(scanf("%d",&n), n)
{
int m = 0;
while(n--)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
x[m] = x1;
ss[m++] = seg(x1, x2, y1, 1);//入邊標記為1
x[m] = x2;
ss[m++] = seg(x1, x2, y2, -1);//出邊標記為-1
}
sort(x, x + m);
sort(ss, ss + m);
int k = 1;
for(int i = 1; i < m; i ++)//去掉重復的點
if(x[i] != x[i-1]) x[k++] = x[i];
memset(sum, 0, sizeof(sum));
memset(cnt, 0, sizeof(cnt));
double ans = 0;
for(int i = 0; i < m - 1; i ++)
{
int l = lower_bound(x, x+k, ss[i].l) - x;
int r = lower_bound(x, x+k, ss[i].r) - x - 1;//因為是以區間建樹，所以r應減一
if(l <= r) update(l, r, ss[i].s, 0 , k-1, 1);
ans += sum[1]*(ss[i+1].h - ss[i].h);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",p++,ans);
}
return 0;
}
