「CODEVS3044」矩形面积求并
题目描述 Description
输入n个矩形，求他们总共占地面积（也就是求一下面积的并）
输入描述 Input Description
可能有多组数据，读到n=0为止(不超过15组)
每组数据第一行一个数n，表示矩形个数(n<=100)
接下来n行每行4个实数x1,y1,x2,y1(0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000)，表示矩形的左下角坐标和右上角坐标
输出描述 Output Description
每组数据输出一行表示答案
样例输入 Sample Input
样例输出 Sample Output
代码
第一次做线段树扫描法的题，网搜各种讲解，发现大多数都讲得太过简洁，不是太容易理解。所以自己打算写一个详细的。看完必会o(∩_∩)o
顾名思义，扫描法就是用一根想象中的线扫过所有矩形，在写代码的过程中，这根线很重要。方向的话，可以左右扫，也可以上下扫。方法是一样的，这里我用的是由下向上的扫描法。
如上图所示，坐标系内有两个矩形。位置分别由左下角和右上角顶点的坐标来给出。上下扫描法是对x轴建立线段树，矩形与y平行的两条边是没有用的，在这里直接去掉。如下图。
现想象有一条线从最下面的边开始依次向上扫描。线段树用来维护当前覆盖在x轴上的线段的总长度，初始时总长度为0。用ret来保存矩形面积总和，初始时为0。
由下往上扫描，扫描到矩形的底边时将它插入线段树，扫描到矩形的顶边时将底边从线段树中删除。而在代码中实现的方法就是，每条边都有一个flag变量，底边为1，顶边为-1。
用cover数组（通过线段树维护）来表示某x轴坐标区间内是否有边覆盖，初始时全部为0。插入或删除操作直接让cover[] += flag。当cover[] > 0 时，该区间一定有边覆盖。
开始扫描到第一条线，将它压入线段树，此时覆盖在x轴上的线段的总长度L为10。计算一下它与下一条将被扫描到的边的距离S（即两条线段的纵坐标之差，该例子里此时为3）。
则 ret += L * S. （例子里增量为10*3=30）
结果如下图
橙色区域表示已经计算出的面积。
扫描到第二条边，将它压入线段树，计算出此时覆盖在x轴上的边的总长度。
例子里此时L=15。与下一条将被扫描到的边的距离S=2。 ret += 30。 如下图所示。
绿色区域为第二次面积的增量。
接下来扫描到了下方矩形的顶边，从线段树中删除该矩形的底边，并计算接下来面积的增量。如下图。
蓝色区域为面积的增量。
此时矩形覆盖的总面积已经计算完成。 可以看到，当共有n条底边和顶边时，只需要从下往上扫描n-1条边即可计算出总面积。
此题因为横坐标包含浮点数，因此先离散化。另外，因为用线段树维护的是覆盖在x轴上的边，而边是连续的，并非是一个个断点，因此线段树的每一个叶子结点实际存储的是该点与下一点之间的距离。
12.25
|
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 |
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; struct data { double x1,x2,y; int flag; }a[801]; double hash[201]; double sum[801]; int col[801]; inline bool cp(data a,data b){return a.y<b.y;} void pushup(int size,int l,int r) { if(col[size])sum[size]=hash[r+1]-hash[l]; else if(l==r)sum[size]=0; else sum[size]=sum[size*2]+sum[size*2+1]; } void update(int L,int R,int flag,int l,int r,int size) { if(L<=l&&R>=r) { col[size]+=flag; pushup(size,l,r); return; } int m=(l+r)/2; if(L<=m)update(L,R,flag,l,m,size*2); if(R>m)update(L,R,flag,m+1,r,size*2+1); pushup(size,l,r); } int main() { int n; while(cin>>n) { if(n==0)break; double x1,y1,x2,y2; for(int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); a[2*i-1].x1=a[2*i].x1=x1; a[2*i-1].x2=a[2*i].x2=x2; a[2*i-1].y=y1;a[2*i].y=y2; a[2*i-1].flag=1;a[2*i].flag=-1; hash[2*i-1]=x1;hash[2*i]=x2; } sort(a+1,a+2*n+1,cp);sort(hash+1,hash+2*n+1); memset(col,0,sizeof(col)); memset(sum,0,sizeof(sum)); double ans=0; for(int i=1;i<=2*n;i++) { int l=lower_bound(hash+1,hash+2*n+1,a[i].x1)-hash; int r=lower_bound(hash+1,hash+2*n+1,a[i].x2)-hash-1; if(l<=r)update(l,r,a[i].flag,1,2*n,1); ans+=sum[1]*(a[i+1].y-a[i].y); } printf("%.2lf\n",ans); } return 0; } |
6.18因为学长要出提交答案题，来重写了一次
|
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 71 72 73 74 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; int n; int t[801]; double hash[805],sum[805]; struct data{double x1,x2,y;int f;}a[805]; inline bool operator<(data a,data b){return a.y<b.y;} int find(double x) { int l=1,r=2*n; while(l<=r) { int mid=(l+r)>>1; if(hash[mid]<x)l=mid+1; else if(hash[mid]==x)return mid; else r=mid-1; } } void pushup(int k,int l,int r) { if(t[k])sum[k]=hash[r+1]-hash[l]; else if(l==r)sum[k]=0; else sum[k]=sum[k<<1]+sum[k<<1|1]; } void update(int k,int l,int r,int x,int y,int f) { if(x==l&&y==r) {t[k]+=f;pushup(k,l,r);return;} int mid=(l+r)>>1; if(y<=mid)update(k<<1,l,mid,x,y,f); else if(x>mid)update(k<<1|1,mid+1,r,x,y,f); else { update(k<<1,l,mid,x,mid,f); update(k<<1|1,mid+1,r,mid+1,y,f); } pushup(k,l,r); } int main() { while(scanf("%d",&n)) { if(n==0)break; memset(t,0,sizeof(t)); memset(sum,0,sizeof(sum)); double x1,y1,x2,y2; for(int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); a[2*i-1].x1=a[2*i].x1=x1; a[2*i-1].x2=a[2*i].x2=x2; a[2*i-1].y=y1;a[2*i].y=y2; a[2*i-1].f=1;a[2*i].f=-1; hash[2*i-1]=x1;hash[2*i]=x2; } sort(hash+1,hash+2*n+1); sort(a+1,a+2*n+1); double ans=0; for(int i=1;i<=2*n;i++) { int l=find(a[i].x1),r=find(a[i].x2)-1; if(l<=r)update(1,1,2*n,l,r,a[i].f); ans+=sum[1]*(a[i+1].y-a[i].y); } printf("%.2lf\n",ans); } return 0; } |
OI 课件=>
[…] 传送门: 传送门: […]
黄学长，我们仰慕您
仰慕黄学长
前排膜拜黄学长
蒟蒻我看完还是不会T_T