http://acm.hdu.edu.cn/showproblem.php?pid=1542
参考了某某大牛的代码。确实代码飘逸,给上注释,怕自己忘了;
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10210 Accepted Submission(s): 4352
2 10 10 20 20 15 15 25 25.5 0
Test case #1 Total explored area: 180.00
/**从下到上枚举每一条边,对x建树,维护总的边在x轴的贡献**/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <string>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
using namespace std;
const int SIZE=2e2+10;
const int maxn=500000;
const int Mod=1e8;
struct Line{
double h,l,r;
int f;
bool operator<(const Line &other)const{
return h<other.h;
}
}l[110];
double sum[SIZE<<2];
int cnt[SIZE<<2];
double X[220];
void pushup(int l,int r,int rt){//cnt等于0时sum表示子树(不包括根节点)的覆盖的长度,else表示整棵树被覆盖了
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 build(int l,int r,int rt){
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
}
int Bin(double key,int n,double X[]){
int l=0,r=n-1;
while(l<=r){
int m=(l+r)>>1;
if(X[m]==key)return m;
if(X[m]<key)l=m+1;
else r=m-1;
}
return -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(R>m)update(L,R,c,rson);
pushup(l,r,rt);
}
int main()
{
int n;
double x1,x2,y1,y2;
int cas=1;
while(scanf("%d",&n)&&n){
for(int i=0;i<n;i++){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
l[i*2]=(Line){y1,x1,x2,1};//1是下边
l[i*2+1]=(Line){y2,x1,x2,-1};//-1是下边
X[2*i]=x1;
X[2*i+1]=x2;
}
sort(X,X+2*n);
sort(l,l+2*n);
int m=1;
for(int i=1;i<2*n;i++){
if(X[i]!=X[i-1])X[m++]=X[i];//去除重复的X,得到需要离散化的最长的边
}
build(0,m-1,1);
double ans=0;
for(int i=0;i<2*n-1;i++){//最大的那一条边无需添加
int L=Bin(l[i].l,m,X);
int R=Bin(l[i].r,m,X)-1;//bin返回的是线段树边界,lr是线段树的线段
//printf("%d %d\n",L,R);
if(L<=R)update(L,R,l[i].f,0,m-1,1);
ans+=sum[1]*(l[i+1].h-l[i].h);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++,ans);
}
return 0;
}
卡了好久