AcWing247亚特兰蒂斯(线段树+扫描线)

题目地址https://www.acwing.com/problem/content/249/

题目描述

有几个古希腊书籍中包含了对传说中的亚特兰蒂斯岛的描述。

其中一些甚至包括岛屿部分地图。

但不幸的是,这些地图描述了亚特兰蒂斯的不同区域。

您的朋友Bill必须知道地图的总面积。

你自告奋勇写了一个计算这个总面积的程序。

输入格式

输入包含多组测试用例。

对于每组测试用例,第一行包含整数n,表示总的地图数量。

接下来n行,描绘了每张地图,每行包含四个数字<span id="MathJax-Element-1-Frame" class="MathJax" data-mathml="x1,y1,x2,y2">x1,y1,x2,y2(不一定是整数),<span id="MathJax-Element-2-Frame" class="MathJax" data-mathml="(x1,y1)">(x1,y1)<span id="MathJax-Element-3-Frame" class="MathJax" data-mathml="(x2,y2)">(x2,y2)分别是地图的左上角位置和右下角位置。

注意,坐标轴 x 轴从上向下延伸,y 轴从左向右延伸。

当输入用例n=0时,表示输入终止,该用例无需处理。

输出格式

每组测试用例输出两行。

第一行输出”Test case #k”,其中k是测试用例的编号,从1开始。

第二行输出“Total explored area: a”,其中a是总地图面积(即此测试用例中所有矩形的面积并,注意如果一片区域被多个地图包含,则在计算总面积时只计算一次),精确到小数点后两位数。

在每个测试用例后输出一个空行。

数据范围

<span id="MathJax-Element-4-Frame" class="MathJax" data-mathml="1≤n≤10000">1n10000
<span id="MathJax-Element-5-Frame" class="MathJax" data-mathml="0≤x1&lt;x2≤100000">0x1<x2100000
<span id="MathJax-Element-6-Frame" class="MathJax" data-mathml="0≤y1&lt;y2≤100000">0y1<y2100000

<span class="MathJax" data-mathml="1≤n≤10000"><span class="MathJax" data-mathml="0≤x1&lt;x2≤100000"><span class="MathJax" data-mathml="0≤y1&lt;y2≤100000">题解:这是一道扫描线+线段树的问题。

<span class="MathJax" data-mathml="1≤n≤10000"><span class="MathJax" data-mathml="0≤x1&lt;x2≤100000"><span class="MathJax" data-mathml="0≤y1&lt;y2≤100000">技术图片

 

我们可以将矩形转变为左边+1,右边-1的操作,每次只需要看看当前大于0的区间的长度再乘以宽度就是当前部分的面积,将所有的面积加起来就可以了

但是因为纵坐标可以不是整数,所以如果直接线段树的话不可以的,首先需要进行离散化处理,将所有的纵坐标进行离散化。这个可以不使用pushdown(),首先pushdown()是在query()和modify()中使用,而我们所要查询的直接tr[u].len就可以了。至于modify(),因为+1和减1是成对出现的,所以不必向下传递。

AC代码

#include<bits/stdc++.h>using namespace std;const int N=1e4+10;struct segment{ double x,y1,y2;//存储的是一个纵坐标区间  int k;}seg[N*2];struct node { int l,r; int cnt;//表示当前区间已经被覆盖了多少次,但是并不向子节点传递,  double len;//表示当前区间大于0的长度 }tr[8*N];vector<double>all;//用于区间横坐标的离散化 int cmp(struct segment a1,struct segment a2){ return a1.x<a2.x;}int find(double y){//返回all中第一个大于等于y的下标再加1,因为原下标是从0开始,而我们需要的是从1开始  return lower_bound(all.begin(),all.end(),y)-all.begin()+1;}void pushup(int u){//向上更新  if(tr[u].cnt) tr[u].len=all[tr[u].r]-all[tr[u].l-1]; else if(tr[u].l!=tr[u].r) tr[u].len=tr[u<<1].len+tr[u<<1|1].len; else tr[u].len=0;}void build(int u,int l,int r){//构建线段树  tr[u].l=l; tr[u].r=r; tr[u].cnt=0; tr[u].len=0; if(l==r){ return ; } int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); return ;}void modify(int u,int l,int r,int d){//区间修改,这里需要注意的是修改[l,r]实际代表的是让all[l-1],all[r]的区间修改  if(tr[u].l>=l&&tr[u].r<=r){ tr[u].cnt+=d; pushup(u); return ; } int mid=tr[u].l+tr[u].r>>1; if(l<=mid) modify(u<<1,l,r,d); if(r>mid) modify(u<<1|1,l,r,d); pushup(u); return ;}int main(){ int n,T=0; while(~scanf("%d",&n)){ if(!n) return 0; all.clear(); for(int i=1,j=1;i<=n;i++){ double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); seg[j++]={x1,y1,y2,1}; seg[j++]={x2,y1,y2,-1}; all.push_back(y1),all.push_back(y2); } sort(seg+1,seg+2*n+1,cmp); sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end()); build(1,1,all.size()-1); double ans=0; for(int i=1;i<=n*2;i++){ if(i>1) ans+=(double)tr[1].len*(seg[i].x-seg[i-1].x); modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k); } cout<<"Test case #"<<++T<<endl; printf("Total explored area: %.2lf\n\n",ans); } return 0;}

写于:202/8/29 12:34

相关文章