#include <bits/stdc++.h> using namespace std; struct Line{ int flag; double x,y1,y2; Line(){} Line(double a,double b,double c,int d) { x = a; y1 = b; y2 = c; flag = d; } bool operator < (const Line &t)const{ return x<t.x; } }; struct N{ int lft,rit,flag; double ll,rr,len; int mid(){return (lft+((rit-lft)>>1));} void fun(int val){ flag+=val; if(flag==0)len=0; else len=rr-ll; } }; N node[1000]; vector<double> y; vector<Line> line; map<double,int> H; void build(int l,int r,int id){ node[id].lft = l; node[id].rit = r; node[id].flag = 0; node[id].len = 0; node[id].ll = y[l]; node[id].rr = y[r]; if(l+1!=r){ int mid = node[id].mid(); build(l,mid,id*2); build(mid,r,id*2+1); } } void update(int l,int r,int id,int val){ int lf = node[id].lft, ri = node[id].rit; if(lf+1==ri)node[id].fun(val);//为两相邻(从小到大)长度边时 else{ int mi = node[id].mid(); if(l<mi)update(l,r,id*2,val); if(r>mi)update(l,r,id*2+1,val); node[id].len = node[id*2].len + node[id*2+1].len; } } int main() { int n,t_cnt=0; while(scanf("%d",&n)&&n){ H.clear(); line.clear(); y.clear(); memset(node,0,sizeof(node)); double x1,x2,y1,y2; for(int i=0;i<n;i++) { scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); line.push_back(Line(x1,y1,y2,1)); line.push_back(Line(x2,y1,y2,-1)); y.push_back(y1); y.push_back(y2); } sort(line.begin(),line.end()); sort(y.begin(),y.end()); y.erase(unique(y.begin(),y.end()),y.end()); for(int i=0;i<(int)y.size();i++)H[y[i]] = i; build(0,(int)y.size()-1,1); double ans = 0; printf("Test case #%d\n",++t_cnt); for(int i=0;i<(int)line.size();i++){//对每条扫描线 if(i!=0)ans+=(line[i].x-line[i-1].x)*node[1].len; update(H[line[i].y1],H[line[i].y2],1,line[i].flag); } printf("Total explored area: %.2lf\n\n",ans); } return 0; }
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句