题意：求 n 个矩形并面积和
tags：扫描线+线段树，模板题
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N=1000+5; int col[N<<3], cnt, res; double X[N<<3], Sum[N<<3], Sum2[N<<3]; //多开一倍，因为 x坐标有两个 struct Seg { double l, r, h; int flag; Seg(){} Seg(double l,double r,double h,int flag):l(l),r(r),h(h),flag(flag){} bool operator <(const Seg & object ) const{ return h < object.h; } }S[N<<2]; void pushup(int ro, int l, int r) { if(col[ro]) //覆盖一次 Sum[ro]=X[r+1]-X[l]; else if(l==r) Sum[ro]=0; else Sum[ro]=Sum[ro<<1]+Sum[ro<<1|1]; if(col[ro]>=2) // 覆盖两次以上 Sum2[ro]=X[r+1]-X[l]; else if(l==r) Sum2[ro]=0; else if(col[ro]==1) Sum2[ro]=Sum[ro<<1] +Sum[ro<<1|1]; else if(col[ro]==0) Sum2[ro]=Sum2[ro<<1] +Sum2[ro<<1|1]; } void update(int L, int R, int c, int ro, int l, int r) // [l,r]当前区间，[L,R]目标区间 { if(L<=l && r<=R) { col[ro] += c; pushup(ro, l, r); return ; } int mid = (l+r)>>1; if(L<=mid) update(L, R, c, ro<<1, l, mid); if(R>mid) update(L, R, c, ro<<1|1, mid+1, r); pushup(ro, l, r); } int binary_find(double x) { int l=1, r=res, ans, mid; while(l<=r) { mid = (l+r)>>1; if(X[mid] >= x) ans=mid, r=mid-1; else l=mid+1; } return ans; } double solve(int n) { cnt = res = 0; for(int i=1; i<=n; ++i) { double x1, y1, x2, y2; scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); S[++cnt]=Seg(x1,x2,y1,1); X[cnt]=x1; S[++cnt]=Seg(x1,x2,y2,-1); X[cnt]=x2; } sort(X+1, X+1+cnt); sort(S+1, S+1+cnt); ++res; for(int i=2; i<=cnt; ++i) { // 去重，x坐标过大的话，就离散化 if(X[i]!=X[i-1]) X[++res]=X[i]; } memset(Sum, 0, sizeof(Sum)); memset(col, 0, sizeof(col)); memset(Sum2, 0, sizeof(Sum2)); double ans=0; for(int i=1; i<cnt; ++i) { int l = binary_find(S[i].l); //二分左端点 int r = binary_find(S[i].r)-1; // 左闭右开,二分右端点 update(l, r, S[i].flag, 1, 1, res); ans += Sum[1]*(S[i+1].h-S[i].h); //矩阵并 //ans += Sum2[1]*(S[i+1].h-S[i].h); //矩阵交集 } return ans; } int main() { int n; while(scanf("%d", &n), n) { printf("%.0f ", solve(n)); } puts("*"); return 0; }