同 POJ1151 这次是两次
#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #include <vector> using namespace std; const int N=1100; double y[N<<1]; struct Line { int co; double x,y1,y2; void fun(double a,double b,double c,int d) { x=a; y1=b; y2=c; co=d; } bool operator<(const Line &e)const { return x<e.x; } }line[N*2]; struct Node { double s,t,len; int co; void change(int o) { co+=o; if(co<2) len=0; else len=t-s; } }; struct Segtree { Node tree[N*8]; void build(int l,int r,int o) { tree[o].s=y[l];tree[o].t=y[r]; tree[o].co=0;tree[o].len=0; if(l+1<r) { int m=(l+r)>>1; build(l,m,o*2); build(m,r,o*2+1); } } void pushup(int o) { tree[o].len=tree[o*2].len+tree[o*2+1].len; } void update(int l,int r,int o,Line e) { if(l+1==r) { tree[o].change(e.co); return; } int m=(l+r)>>1; if(e.y1<tree[o*2].t)update(l,m,o*2,e); if(e.y2>tree[o*2+1].s)update(m,r,o*2+1,e); pushup(o); } }seg; int main() { int n,T; scanf("%d",&T); while(T--) { scanf("%d",&n); int cnt=0; for(int i=0;i<n;i++) { double x1,x2,y1,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); line[++cnt].fun(x1,y1,y2,1); y[cnt]=y1; line[++cnt].fun(x2,y1,y2,-1); y[cnt]=y2; } sort(line+1,line+cnt+1); sort(y+1,y+cnt+1); int d=1; for(int i=2;i<=cnt;i++) if(y[i]!=y[i-1])y[++d]=y[i]; double ans=0; seg.build(1,d,1); seg.update(1,d,1,line[1]); for(int i=2;i<=cnt;i++) { ans+=(line[i].x-line[i-1].x)*seg.tree[1].len; seg.update(1,d,1,line[i]); } printf("%.2f ",ans); } return 0; }