# HDU1542-Atlantis(扫描线+离散化个人小结)

2018-01-30 10:44:46来源:网络收集作者:管理员人点击

Atlantis

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 15590Accepted Submission(s): 6400

Problem Description
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 contains four 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 it.

Output
For each test case, your program should output one section. The first line of each section must be “Test case #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

for(int i=1;i

void pushup(int l,int r,int root)
{
if(tree[root].vis)tree[root].ans=posx[r+1]-posx[l];
else if(l==r)tree[root].ans=0;
else tree[root].ans=tree[root*2].ans+tree[root*2+1].ans;
}
void update(int nl,int nr/*目标区间*/,int add,int l,int r,int root)
{
if(nl==l&&nr==r)
{
pushup(nl,nr,root);
return ;
}
int mid=(l+r)/2;
pushup(l,r,root);
}
for(int i=0;i{
int l=lower_bound(posx,posx+num,edge[i].xl)-posx;/*利用low返回下标*/
int r=lower_bound(posx,posx+num,edge[i].xr)-posx-1;
update(l,r,edge[i].flag,0,num-1,1);
ans+=tree[1].ans*(edge[i+1].h-edge[i].h);
}

1.如果当前节点有标记，那么说明我们当前线段对答案是有贡献的，tree[root].ans=posx[r+1]-posx[l]。这里是等于，因为线段对于答案的贡献是覆盖，而不是叠加，如果一条大边覆盖了小边，那么对答案贡献的，只需要取大边的值即可。
2.如果当前节点没有标记，并且区间长度为0，tree[root].ans=0。这里说一下区间左开右闭的性质，假设我们有一颗线段树，管理区间[1,4].那么将其子节点展开：

3.和线段树类似的根节点由子节点更新。

ans+=tree[1].ans*(edge[i+1].h-edge[i].h);

AC代码：

#include
#include
#include
#define met(s,k) memset(s,k,sizeof s)
#define scan(a) scanf("%d",&a)
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int cont/*原始边数*/,num/*离散化后的边数*/;
double posx[maxn]/*离散后的点*/;
struct Tree
{
double ans;
int vis;
}tree[maxn];
struct Edge
{
double xl,xr,h;
int flag;
Edge(){};
Edge(double a,double b,double c,int d) : xl(a),xr(b),h(c),flag(d){}
bool operator< (const Edge &a)const{
return h}
}edge[maxn];
void pushup(int l,int r,int root)
{
if(tree[root].vis)tree[root].ans=posx[r+1]-posx[l];
else if(l==r)tree[root].ans=0;
else tree[root].ans=tree[root*2].ans+tree[root*2+1].ans;
}
void update(int nl,int nr/*目标区间*/,int add,int l,int r,int root)
{
if(nl==l&&nr==r)
{
pushup(nl,nr,root);
return ;
}
int mid=(l+r)/2;
pushup(l,r,root);
}
int main()
{
int cas=0,n;
while(scan(n),n)
{
double ans=0;
met(tree,0);
cont=0;
num=1;/*初始化*/
for(int i=0;i {
double x,y,z,m;
scanf("%lf%lf%lf%lf",&x,&y,&z,&m);
edge[cont]=Edge(x,z,y,1);
posx[cont++]=x;
edge[cont]=Edge(x,z,m,-1);
posx[cont++]=z;
}
sort(posx,posx+cont);
sort(edge,edge+cont);
for(int i=1;i for(int i=0;i {
int l=lower_bound(posx,posx+num,edge[i].xl)-posx;/*利用low返回下标*/
int r=lower_bound(posx,posx+num,edge[i].xr)-posx-1;
update(l,r,edge[i].flag,0,num-1,1);
ans+=tree[1].ans*(edge[i+1].h-edge[i].h);
}
printf("Test case #%d/nTotal explored area: %0.2f/n",++cas,ans);
printf("/n");
}
return 0;
}