本文共 2197 字，大约阅读时间需要 7 分钟。
题解+扫描线讲解：
#include #include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define sd(x) scanf("%d",&(x))#define sl(x) scanf("%lld",&(x))#define slf(x) scanf("%lf",&(x))#define scs(s) scanf("%s",s)#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)#define lowbit(x) x&(-x)#define ls now<<1#define rs now<<1|1#define lson l,mid,ls#define rson mid+1,r,rs#define All L,Rusing namespace std;const int maxn=2222;struct node{ double l,r,h; int d; bool operator <(const node cmp) const{ return h >1; lazy[now]=tree[now]=0; if(l==r) return ; built(lson); built(rson);}void pushdown(int now,int l,int r){ int mid=(l+r)>>1; if(lazy[now]!=-1) { lazy[ls]=lazy[rs]=lazy[now]; tree[ls]=lazy[ls]?Hash[mid+1]-Hash[l]:0; tree[rs]=lazy[rs]?Hash[r+1]-Hash[mid+1]:0; }}void pushup(int now,int l,int r){ if(lazy[ls]==-1||lazy[rs]==-1||(lazy[rs]!=lazy[ls])) lazy[now]=-1; else lazy[now]=lazy[ls]; tree[now]=tree[ls]+tree[rs];}void update(int l,int r,int now,int L,int R,int c){ int mid=(l+r)>>1; if(L<=l&&r<=R) { if(lazy[now]!=-1) { lazy[now]+=c; tree[now]=lazy[now]?Hash[r+1]-Hash[l]:0; return ; } } pushdown(now,l,r); if(L<=mid) update(lson,All,c); if(R>mid) update(rson,All,c); pushup(now,l,r);}int bin(double key,int n,double d[]){ int l=1,r=n; while(r>=l) { int m=(r+l)/2; if(d[m]==key) return m; else if(d[m]>key) r=m-1; else l=m+1; }}int main(){ int t,tot=0; while(sd(t)&&t) { int n=0,m=0; double x1,x2,y1,y2; rep(i,1,t) { slf(x1),slf(y1),slf(x2),slf(y2); Hash[++n]=x1; Hash[++n]=x2; e[++m]=(node){x1,x2,y1,1}; e[++m]=(node){x1,x2,y2,-1}; } sort(e+1,e+1+m); sort(Hash+1,Hash+1+n); n=unique(Hash+1,Hash+1+n)-Hash-1; built(1,n-1,1); double ans=0; rep(i,1,m-1) { int l=lower_bound(Hash+1,Hash+1+n,e[i].l)-Hash; int r=lower_bound(Hash+1,Hash+1+n,e[i].r)-Hash-1; if(l<=r) update(1,n-1,1,l,r,e[i].d); ans+=tree[1]*(e[i+1].h-e[i].h); } printf("Test case #%d\nTotal explored area: %.2lf\n\n",++tot,ans); } return 0;}
转载于:https://www.cnblogs.com/minun/p/11295885.html