POJ 1151 Atlantis（经典的线段树扫描线，求矩阵面积并）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R
/*
AC
一开始一直WA的原因是，hashx写成了int型！！！第一次用的是直接单点更新，这次用区间更新写写看
*/
using namespace std;
const int maxn=;
int n;
double x1,y1,x2,y2;
//题目中有误，题目说的是(x1,y1)为矩形的左上端点，(x2,y2)为矩形的右下端点，
//但是给出的值y1<y2。。。也就是说(x1,y1)为矩形的左下端点，(x2,y2)为矩形的右上端点
double hashx[maxn<<];
int idx;
int mark[maxn<<];
double sum[maxn<<];
struct Line{
double y,l,r;
int tp;
bool operator<(const Line tmp)const{
return y<tmp.y;
}
}line[maxn<<];struct Node{
double sum;
int mark;
}tree[maxn<<];void build(int rt,int L,int R){
tree[rt].sum=tree[rt].mark=;
if(L==R){
return ;
}
int mid=(L+R)>>;
build(rt<<,L,mid);
build(rt<<|,mid+,R);
}void pushUp(int rt,int L,int R){
if(tree[rt].mark){
tree[rt].sum=hashx[R+]-hashx[L];
}
else{
if(L==R)
tree[rt].sum=;
else
tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;
}
}
void update(int rt,int L,int R,int l,int r,int val){
if(L==R){
//原本写了个tree[rt].mark。。。
tree[rt].mark+=val;
pushUp(rt,L,R);
return;
}
int mid=(L+R)>>;
if(r<=mid)
update(lson,l,r,val);
else if(l>mid)
update(rson,l,r,val);
else{
update(lson,l,mid,val);
update(rson,mid+,r,val);
}
pushUp(rt,L,R);
}
//二分搜索对应的映射，也可以用map建立double-int的映射关系
int binarySearch(double x){
int l=,r=n+,mid; //注意：l初试为0，r初试为n+1。否则若是1和n的话，若搜索的值为hashx[1]或者hashx[n]就错了。
while (r-l>) //这里若为r>l的话，就会陷入死循环。举例：l=1,r=2,mid=1,x>=hashx[1]。
{
mid=(l+r)>>;
if (hashx[mid]<=x) l=mid;
else r=mid;
}
return l;
}int main()
{
int a,b,t=;
while(scanf("%d",&n),n){
idx=;
t++;
for(int i=;i<=n;i++){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[*i-].y=y1;line[*i-].l=x1;line[*i-].r=x2;line[*i-].tp=;
line[*i].y=y2;line[*i].l=x1;line[*i].r=x2;line[*i].tp=-;
hashx[++idx]=x1;
hashx[++idx]=x2;
}
n=n*;
build(,,n);
sort(line+,line++n);
sort(hashx+,hashx+idx+);
double ans=;
for(int i=;i<=n;i++){
ans+=tree[].sum*(line[i].y-line[i-].y);
a=binarySearch(line[i].l);
b=binarySearch(line[i].r)-;
update(,,n,a,b,line[i].tp);
}
printf("Test case #%d\n",t);
printf("Total explored area: %.2lf\n\n",ans);
}
return ;
}

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
/*
AC
*/
using namespace std;
const int maxn=;
int n;
double x1,y1,x2,y2;
//题目中有误，题目说的是(x1,y1)为矩形的左上端点，(x2,y2)为矩形的右下端点，
//但是给出的值y1<y2。。。也就是说(x1,y1)为矩形的左下端点，(x2,y2)为矩形的右上端点
double hashx[maxn<<];
int idx;
int mark[maxn<<];
double sum[maxn<<];
struct Line{
double y,l,r;
int tp;
bool operator<(const Line tmp)const{
return y<tmp.y;
}
}line[maxn<<];struct Node{
double sum;
int mark;
}tree[maxn<<];void build(int rt,int L,int R){
tree[rt].sum=tree[rt].mark=;
if(L==R){
return ;
}
int mid=(L+R)>>;
build(rt<<,L,mid);
build(rt<<|,mid+,R);
}void pushUp(int rt){
tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;
}
void update(int rt,int x,int L,int R,int val){
if(L==R){
tree[L].mark+=val;
//mark[x]+=val;
if(tree[L].mark)
tree[rt].sum=hashx[x+]-hashx[x];
else
tree[rt].sum=;
return;
}
int mid=(L+R)>>;
if(x<=mid)
update(rt<<,x,L,mid,val);
else
update(rt<<|,x,mid+,R,val);
pushUp(rt);
}
//二分搜索对应的映射，也可以用map建立double-int的映射关系
int binarySearch(double x){
int l=,r=n+,mid; //注意：l初试为0，r初试为n+1。否则若是1和n的话，若搜索的值为hashx[1]或者hashx[n]就错了。
while (r-l>) //这里若为r>l的话，就会陷入死循环。举例：l=1,r=2,mid=1,x>=hashx[1]。
{
mid=(l+r)>>;
if (hashx[mid]<=x) l=mid;
else r=mid;
}
return l;
}int main()
{
int a,b,t=;
while(scanf("%d",&n),n){
idx=;
t++;
memset(mark,,sizeof(mark));
for(int i=;i<=n;i++){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[*i-].y=y1;line[*i-].l=x1;line[*i-].r=x2;line[*i-].tp=;
line[*i].y=y2;line[*i].l=x1;line[*i].r=x2;line[*i].tp=-;
hashx[++idx]=x1;
hashx[++idx]=x2;
}
n=n*;
build(,,n);
sort(line+,line++n);
sort(hashx+,hashx+idx+);
double ans=;
for(int i=;i<=n;i++){
ans+=tree[].sum*(line[i].y-line[i-].y);
a=binarySearch(line[i].l);
b=binarySearch(line[i].r)-;
for(int j=a;j<=b;j++)
update(,j,,n,line[i].tp);
}
printf("Test case #%d\n",t);
printf("Total explored area: %.2lf\n\n",ans);
}
return ;
}