题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1542
分析：离散化+扫描线+线段树
#pragma comment(linker,"/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 10007 #define inf 0x3f3f3f3f #define N 2015 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; struct line { double l,r,h; int d; line(){} line(double l,double r,double h,int d):l(l),r(r),h(h),d(d){} bool operator<(const line &a)const { return h<a.h; } }s[N]; double sum[N<<2],has[N]; int col[N<<2]; void Pushup(int l,int r,int rt) { if(col[rt])sum[rt]=has[r+1]-has[l];//每个点表示的是has[i]~has[i+1]的长度，故has[r+1]-has[l] else if(l==r)sum[rt]=0;//节点没有子节点加上来，故清零 else sum[rt]=sum[rt<<1]+sum[rt<<1|1];//加上子孙节点被覆盖着的线段长度 } void update(int L,int R,int d,int l,int r,int rt) { if(L<=l&&r<=R) { col[rt]+=d; Pushup(l,r,rt); return; } int m=(l+r)>>1; if(L<=m)update(L,R,d,lson); if(m<R)update(L,R,d,rson); Pushup(l,r,rt); } int bin(double key,double a[],int n) { int l=0,r=n-1; while(l<=r) { int m=(l+r)>>1; if(a[m]==key)return m; if(a[m]>key)r=m-1; else l=m+1; } return -1; } int main() { int n,cas=1; double x1,y1,x2,y2; while(scanf("%d",&n)&&n) { int k=0; for(int i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); has[k]=x1; s[k++]=line(x1,x2,y1,1); has[k]=x2; s[k++]=line(x1,x2,y2,-1); } sort(s,s+k); sort(has,has+k); int m=1; for(int i=1;i<k;i++)//去重 if(has[i]!=has[i-1])has[m++]=has[i]; double ans=0; for(int i=0;i<k;i++) { int L=bin(s[i].l,has,m); int R=bin(s[i].r,has,m)-1; update(L,R,s[i].d,0,m-1,1);//区间更新 ans+=sum[1]*(s[i+1].h-s[i].h);//sum[1]表示被覆盖着的总长度 } printf("Test case #%d Total explored area: %.2lf ",cas++,ans); } }