POJ1151 Atlantis(线段树,扫描线,离散化,矩形面积并)

2023-10-06 00:00

本文主要是介绍POJ1151 Atlantis(线段树,扫描线,离散化,矩形面积并),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:
Atlantis
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 23220 Accepted: 8657
Description

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.
Input

The input 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

2
10 10 20 20
15 15 25 25.5
0
Sample Output

Test case #1
Total explored area: 180.00
Source

Mid-Central European Regional Contest 2000
[Submit] [Go Back] [Status] [Discuss]

思路:

这题是我线段树扫描线的第一题,题目给了n个矩形,每个矩形给了左下角右上角的坐标,矩形可能会重叠,求的是矩形最后的面积。因为变化范围比较大,我们要用到离散化,离散化就不说了,重点说一说扫描线的过程:
下面有个矩形

现在假设我们有一根线,从下往上开始扫描

  • 如图所示,我们可以把整个矩形分成如图各个颜色不同的小矩形,那么这个小矩形的高就是我们扫过的距离,那么剩下了一个变量,那就是矩形的长一直在变化。
  • 我们的线段树就是为了维护矩形的长,我们给每一个矩形的上下边进行标记,下面的边标记为1,上面的边标记为-1,每遇到一个矩形时,我们知道了标记为1的边,我们就加进来这一条矩形的长,等到扫描到-1时,证明这一条边需要删除,就删去,利用1和-1可以轻松的到这种状态。
  • 还要注意这里的线段树指的并不是线段的一个端点,而指的是一个区间,所以我们要计算的时候r+1和r-1
  • 再提一下离散化,离散化就是把一段很大的区间映射到一个小区间内,这样会节省大量空间,要进行离散化,我们先对端点进行排序,然后去重,然后二分找值就可以了

具体的请结合代码分析:

代码

#include <cstdio>
#include <cstring>
#include <cctype>
#include <string>
#include <set>
#include <iostream>
#include <stack>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define N 220
#define ll long long
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct Seg
{double l,r,h;int f;Seg() {}Seg(double a,double b,double c,int d):l(a),r(b),h(c),f(d) {}bool operator < (const Seg &cmp) const{return h<cmp.h;}
} e[N];
struct node
{int cnt;double len;
} t[N<<2];
double X[N];
void pushdown(int l,int r,int rt)
{if(t[rt].cnt)//当前的边被标记,就把当前的长度加上t[rt].len=X[r+1]-X[l];else if(l==r)//当为一个点的时候长度为0t[rt].len=0;else//其他情况把左右两个区间的值加上t[rt].len=t[rt<<1].len+t[rt<<1|1].len;
}
void update(int L,int R,int l,int r,int rt,int val)
{if(L<=l&&r<=R){t[rt].cnt+=val;//加上标记的值pushdown(l,r,rt);//像下更新节点return;}int m=(l+r)>>1;if(L<=m) update(L,R,lson,val);if(R>m) update(L,R,rson,val);pushdown(l,r,rt);
}
int main()
{int n,q=1;double a,b,c,d;while(~scanf("%d",&n)&&n){mem(t,0);int num=0;for(int i=0; i<n; i++){scanf("%lf%lf%lf%lf",&a,&b,&c,&d);X[num]=a;e[num++]=Seg(a,c,b,1);//矩形下面用1来标记吗X[num]=c;e[num++]=Seg(a,c,d,-1);//上面用-1来标记}sort(X,X+num);//用于离散化sort(e,e+num);//把矩形的边的纵坐标从小到大排序int m=unique(X,X+num)-X;double ans=0;for(int i=0; i<num; i++){int l=lower_bound(X,X+m,e[i].l)-X;//找出离散化以后的值int r=lower_bound(X,X+m,e[i].r)-X-1;update(l,r,0,m,1,e[i].f);ans+=t[1].len*(e[i+1].h-e[i].h);}printf("Test case #%d\nTotal explored area: %.2lf\n\n",q++,ans);}return 0;
}

这篇关于POJ1151 Atlantis(线段树,扫描线,离散化,矩形面积并)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/152334

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

HDU4737线段树

题目大意:给定一系列数,F(i,j)表示对从ai到aj连续求或运算,(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

圆与线段的交点

poj 3819  给出一条线段的两个端点,再给出n个圆,求出这条线段被所有圆覆盖的部分占了整条线段的百分比。 圆与线段的交点 : 向量AB 的参数方程  P = A + t * (B - A)      0<=t<=1 ; 将点带入圆的方程即可。  注意: 有交点 0 <= t <= 1 ; 此题求覆盖的部分。 则 若求得 t  满足 ; double ask(d

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja