http://acm.hdu.edu.cn/showproblem.php?pid=1542
//线段树+离散化计算覆盖矩形的面积并
//经典题目
#include <iostream>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdio.h>
using namespace std;
typedef pair<double,int> mypair;//用于将double型的长度和int型的区间关联
double x[201],y[201],mx[201],my[201];//x,y存储原始数据，mx,my存储排序后的数据
map<double,int> m;
double lenth;//用于计算每回合覆盖的总长度
class tree //segment tree
{
public:
int begin,end,mid;
bool isoccupied;
tree *left,*right;
tree(){}
tree(int a,int b)//create tree
{
begin=a;
end=b;
mid=(a+b)/2;
if(begin+1!=end)//若不是叶子节点，则递归建立线段树
{
left=new tree(a,mid);
right=new tree(mid,b);
}
}
void clear()//clear tree
{
isoccupied=false;
if(begin+1!=end)
{
left->clear();
right->clear();
}
}
void modify(int a,int b)//modify tree
{
if(a>b)
swap(a,b);
if(a==begin && b==end)//遇到正好标记的段，返回，不需要向下标记
{
isoccupied=true;
return;
}
if(begin+1==end)
return ;
if(b<=mid)
left->modify(a,b);
else if(a>=mid)
right->modify(a,b);
else
{
left->modify(a,mid);
right->modify(mid,b);
}
}
void sum()//compute sum
{
if(isoccupied==true) //只计算正好标记的段，防止重复计算
{
lenth+=my[end]-my[begin];
return ;
}
if(begin+1==end)
{
return;
}
else
{
left->sum();
right->sum();
}
}
};
int main()
{
int i=1,n,j,k;
double result;
while(scanf("%d",&n),n)
{
result=0;//每次都要初始化
m.clear();//清空树
for(j=0;j<n;j++)
{
scanf("%lf %lf %lf %lf",&x[2*j],&y[2*j],&x[2*j+1],&y[2*j+1]);
}
for(j=0;j<2*n;j++)
{
mx[j]=x[j];
my[j]=y[j];
}
sort(mx,mx+2*n);
sort(my,my+2*n);
for(j=0;j<2*n;j++)//将y坐标与区间关联，查找方便
m.insert(mypair(my[j],j));
tree *root=new tree(0,2*n-1);//建立线段树,注意从0开始，因为my数组是从0开始的，要保持照应
for(j=0;j<2*n-1;j++) //注意是2*n-1,不是2*n
{
double temp=mx[j+1]-mx[j];//横向分割段长
lenth=0; //纵向段长清零
root->clear(); //每次都要重新计算纵向段长
for(k=0;k<n;k++)
{
if(x[2*k]<=mx[j] && x[2*k+1]>=mx[j+1])//当某矩形纵向包含当前分割段时，说明它包含要计算的块
root->modify(m[y[2*k]],m[y[2*k+1]]);//调整y[2*k],y[2*k+1]对应的段
}
root->sum();
result+=temp*lenth;
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",i++,result);
}
}
posted on 2011-05-27 23:45
大大木马 阅读(673)
评论(0) 编辑 收藏 引用