HDU 1542(矩形面积并） - c++编程基础

Atlantis
Problem Description
已知Atlantis的地图由许多矩形构成，求它们的面积并。

Input
题目有多组数据，每组数据的开头有一个整数n(1<=n<=100)，表示地图数，接下来n行,每行4个小数 x1;y1;x2;y2 (0<=x1 数据以0结束

Output
对于每组数据，你需要输出一行 “Test case #k”,k表示第k组数据(从1开始).第二行为“Total explored area: a”,a为面积并（保留2位小数），
每组数据后，请输出一个回车。

Sample Input
2
10 10 20 20
15 15 25 25.5
0

Sample Output
Test case #1
Total explored area: 180.00

矩形面积并入门题，
首先把直线拆成上边和下边，按高度排序，
横坐标离散化，建立线段树。 www.2cto.com
cnt[]表示某条线段被覆盖的次数，sum[]表示一条线段被覆盖的长度
我们在计算cnt[]时,没修改1个cnt[],就用pushup把sum[]更新，得到程序1：

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (2000+10)
#define MAXT (1000*2*10)
#define Lson (x<<1)
#define Rson ((x<<1)^1)
int tt,n,size;
double x[MAXN];
struct SegMent
{
double x1,x2,h;
int type;
SegMent(){}
SegMent(double _x1,double _x2,double _h,int _type):x1(_x1),x2(_x2),h(_h),type(_type){}
friend bool operator<(const SegMent a,const SegMent b){return a.h }a[MAXN];
map hpos;
double len[MAXT];
struct SegMentTree
{
int n,M,cnt[MAXT];
double sum[MAXT];
int mark[MAXT];
void fillchar(int _n)
{
n=_n;
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
memset(mark,0,sizeof(mark));
M=1;while (M-2 x[0]=0;memset(len,0.0,sizeof(len));
for (int i=M+1;i<=M+size;i++) len[i]=x[i-M]-x[i-M-1];
for (int i=M-1;i>0;i--) len[i]=len[i<<1]+len[(i<<1)^1];
}
void pushdown(int x)
{
if (x>>1) pushdown(x>>1);
if (mark[x])
{
mark[Lson]+=mark[x];
cnt[Lson]+=mark[x];
mark[Rson]+=mark[x];
cnt[Rson]+=mark[x];
mark[x]=0;
}
}
void pushup(int x)
{
// pushdown(x);cout< // cout<
sum[x]=cnt[x] len[x]:(x>=M 0:sum[Lson]+sum[Rson]);
}
void update(int x)
{
for (;x;x>>=1)
{
// cout<<"push "< pushup(x);
}
}

void insert(int l,int r,int c)
{
int ll=l-1+M,rr=r+1+M;
for (l=l-1+M,r=r+1+M,pushdown(l>>1),pushdown(r>>1);l^r^1;l>>=1,r>>=1)
{
if (~l&1) {cnt[l+1]+=c;update(l+1);/*mark[l+1]+=c;*/} /*改变sum的值 */
if (r&1) {cnt[r-1]+=c;update(r-1);/* mark[r-1]+=c;*/}
}
// update(ll);update(rr); //向上传递
}
void print()
{
cout<<"cnt ";
for (int i=1;i<=M*2;i++) if (cnt[i]) cout< cout< cout<<"sum ";
for (int i=1;i<=M*2;i++) if (sum[i]) cout< cout< cout<<"Mark ";
for (int i=1;i<=M*2;i++) if (mark[i]) cout< cout< }
}t;

int main()
{
// freopen("Hdu1542.in","r",stdin);
tt=0;
while (scanf("%d",&n)!=EOF)
{
tt++;
if (!n) break;
for (int i=1;i<=2*n;i+=2)
{
scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].h,&a[i].x2,&a[i+1].h);
a[i+1].x1=a[i].x1; a[i+1].x2=a[i].x2;
a[i].type=1;a[i+1].type=-1;
x[i]=a[i].x1;x[i+1]=a[i].x2;
}
sort(a+1,a+2*n+1);
// for (int i=1;i<=2*n;i++) cout<
sort(x+1,x+2*n+1);
size=unique(x+1,x+2*n+1)-(x+1);
// for (int i=1;i<=size;i++) cout<
for (int i=1;i<=size;i++) hpos[x[i]]=i;

t.fillchar(size);
/* for (int i=1;i<=t.M*2;i++) cout< cout< */ /*
t.insert(1,3,1);t.print();
t.insert(2,4,2);
cout< cout< t.print();
*/
// t.insert(2,3,1);
/*
t.insert(2,3,1);
t.print();
t.in

HDU 1542(矩形面积并）(一)