http://acm.hust.edu.cn/vjudge/problem/10769
给n张海报，在每张海报上剪掉一个矩形，求面积并
把剪块的海报分成四个矩形，就是普通的求面积并问题了
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 50000+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m; int hh[MAXN],col[MAXN<<3],len[MAXN<<3]; struct node { int l,r,x,c; node(){} node(int a,int b,int c,int d):l(a),r(b),x(c),c(d){} bool operator < (const node &b) const { return x<b.x; } }a[MAXN<<3]; void PushUp(int rt,int l,int r) { if(col[rt]) { len[rt] = hh[r+1] - hh[l]; } else if(l==r) len[rt] = 0; else { len[rt] = len[ls]+len[rs]; } } void update(int val,int L,int R,int l,int r,int rt) { if(L<=l && r<=R) { col[rt] += val; PushUp(rt,l,r); return; } int mid = (l+r)>>1; if(L <= mid) update(val,L,R,l,mid,ls); if(R > mid) update(val,L,R,mid+1,r,rs); PushUp(rt,l,r); } int main() { int i,j,k,t,kase=1; while(~sf("%d",&n) && n) { int v=0; LL sum = 0; for(i=0;i<n;i++) { int x1,y1,x2,y2; int X1,Y1,X2,Y2; sf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&X1,&Y1,&X2,&Y2); if(x1!=X1) { hh[v] = y1; a[v++] = node(y1,y2,x1,1); hh[v] = y2; a[v++] = node(y1,y2,X1,-1); } if(x2!=X2) { hh[v] = y1; a[v++] = node(y1,y2,X2,1); hh[v] = y2; a[v++] = node(y1,y2,x2,-1); } if(y1!=Y1) { hh[v] = y1; a[v++] = node(y1,Y1,X1,1); hh[v] = Y1; a[v++] = node(y1,Y1,X2,-1); } if(y2!=Y2) { hh[v] = Y2; a[v++] = node(Y2,y2,X1,1); hh[v] = y2; a[v++] = node(Y2,y2,X2,-1); } } sort(hh,hh+v); sort(a,a+v); int d = 1; for(i=1;i<v;i++) { if(hh[i]!=hh[i-1]) hh[d++] = hh[i]; } mem(len,0); mem(col,0); for(i=0;i<v-1;i++) { int l = lower_bound(hh,hh+d,a[i].l)-hh; int r = lower_bound(hh,hh+d,a[i].r)-hh-1; update(a[i].c,l,r,0,d-1,1); sum+=len[1]*((long long)a[i+1].x-a[i].x); //pf("%lf %lf ",sum,len[1]); } pf("%I64d ",sum); } return 0; }