Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Problem Description
Input
The input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don’t process it.
Output
For each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.
Sample Input
Sample Output
Source
Solution
扫描线。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; const int N=205; int n; double pos[N]; struct node{double l,r,h;int f;}a[N]; struct Tree{int flag;double num;}tree[N*8]; bool cmp(node a,node b) { return a.h<b.h;} void build(int l,int r,int id) { tree[id].flag=0;tree[id].num=0; if (l==r) return; int mid=(l+r)/2; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void calc(int id,int l,int r) { if (tree[id].flag>0) tree[id].num=pos[r+1]-pos[l]; else if (l==r) tree[id].num=0;else tree[id].num=tree[id<<1].num+tree[id<<1|1].num; } void change(int x,int y,int l,int r,int id,int d) { if (l>y||r<x) return; if (x<=l&&r<=y) { tree[id].flag+=d; calc(id,l,r); return; } int mid=(l+r)/2; change(x,y,l,mid,id<<1,d); change(x,y,mid+1,r,id<<1|1,d); calc(id,l,r); } int main() { int T=0; while (scanf("%d",&n)!=EOF) { if (n==0) break; for (int i=1;i<=n;i++) { double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); a[i].l=x1;a[i].r=x2;a[i].h=y1;a[i].f=1; a[n+i].l=x1;a[n+i].r=x2;a[n+i].h=y2;a[n+i].f=-1; pos[i]=x1;pos[n+i]=x2; } sort(a+1,a+n*2+1,cmp); sort(pos+1,pos+2*n+1); int tot=unique(pos+1,pos+2*n+1)-pos-1; build(0,tot,1); double ans=0; for (int i=1;i<=n*2;i++) { int l=lower_bound(pos+1,pos+tot+1,a[i].l)-pos; int r=lower_bound(pos+1,pos+tot+1,a[i].r)-pos-1; change(l,r,0,tot,1,a[i].f); ans+=(a[i+1].h-a[i].h)*tree[1].num; } printf("Test case #%d\n",++T); printf("Total explored area: %.2f\n\n",ans); } return 0; } |
