atlantis专题

HDU 1542 POJ 1151 Atlantis(线段树+扫描线）

题目地址：HDOJ地址：HDU 1542 POJ 地址：POJ 1151 第一发扫描线。。费了好大一番功夫。。构思用了半天。。写出来调试成功用了半天。。。真是弱渣。。所谓扫描线就是从上往下或从下往上扫描，每到一个边，就进行增或删的处理。最后出来的值就是总的面积。对于求面积并的问题，可以参考这篇博客（博客地址），讲的不错。具体实现过程是用lazy标记此时的边数量，如果大于0，说明这个地方

Atlantis 线段树扫描线--面积并

Atlantis Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 16755 Accepted: 6391 Description There are several ancient Greek texts that contain descript

POJ 1151 Atlantis 线段树/矩形面积并

题意：求矩形的面积并。题解：求矩形的并，由于矩形的位置可以多变，因此矩形的面积一下子不好求这个时候，可以采用“分割”的思想，即把整块的矩形面积分割成几个小矩形的面积，然后求和就行了这里我们可以这样做，把每个矩形投影到 y 坐标轴上来然后我们可以枚举矩形的 x 坐标，然后检测当前相邻 x 坐标上 y 方向的合法长度，两种相乘就是面积然后关键就是如何用线段树来

2018.01.26【NOIP普及组】模拟赛D组——游戏(atlantis.pas/cpp)

题目描述 Atlantis Island 沉没以前，传说中的猫老大和 King 是好朋友……King 很喜欢赌博，这次 King和老朋友猫老大多年不见，于是便邀请猫老大来玩一个游戏,猫老大应邀参加了。 King 拿出了 n 块黄金(n<10^1000002)，猫老大暗自想：咋来这么多钱的„„,现在 King 和猫老大轮流从黄金中拿走一些,每人每次拿走的块数是 2 的次方(例如 1,2,4,8

POJ 1151 Atlantis

首先，我得吐个槽。陶叔果然是个诚实的孩子，今天的题简直坑爆了好么？先说A题，翻了一遍题目，觉得A题(SPOJ SUB_PROB)就是个KMP的模板题，心中大喜，套模板，欲A之，怎奈何居然是WA（我还提交了三遍T_T，再不济你给个TLE我也可以接受啊）。于是重新读题，发现应该拿AC自动机来搞！！！瞄一眼Rank，分析一下局势，决定不理A题了，开了E题(Aizu 0024)。由于E题是签到水题

hud 1542——Atlantis hdu

扫描线问题第一道扫描线，还是照着别人代码搞了一下。树的内容不多，所以没放进结构体内。 map的映射挺方便，效率也不会很差。 //0MS 368K G++#include<map>#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define

HDOJ-1542 Atlantis 扫描线

扫描线算法的核心思想在于使用线段树对扫描线线段的长度进行维护。因此，如果平行于x轴做扫描线，那么就需要以所有的端点的x坐标为端点，以这些端点组成的线段为线段树叶子节点存储的对象，从而对扫描线的长度进行维护。另外，说明下代码中cnt的作用。这个标记代表看似是一个lazy tag，但又不是，因为这个标记是不会往子节点传的（及不能使用pushdown操作）。扫描线算法中，叶子节点（代表的是每一个小段

【线段树】[POJ Atlantis] 线段树扫描线

题目：题目链接：[POJ Atlantis] 题解：（这个题作为学习线段树的尾巴，，，结果还是学了好长时间）先安利一下sdau_blue大佬的优秀博客，太有用了。这个题就是有许多的矩形进行随意放置在二维平面内，重叠的面积只算一次，求总面积。在这里就是离散化处理横坐标，对于纵坐标进行结构体处理一下，然后再以横坐标作为线段(区间)，对横坐标线段进行扫描，扫描的作用是每次更新下底边总

Atlantis HDU - 1542 （扫描线 + 线段树）

https://cn.vjudge.net/problem/HDU-1542 题意求矩形覆盖的面积思路模板题 #include <bits/stdc++.h>using namespace std;const int maxn = 210;int n,cnt,num,p;double ls[maxn*2],ans;struct edg ///边{double l,r,h

[poj 1151] Atlantis：扫描线+线段树求面积并

想做APIO 2012 Kunai ，我要把虐过我的题虐回去。把问题转化为了平面中线段的并，或者说面积并。听说这道题要用线段树，大概就是这里了？除了二维线段树，我没有想到什么时间复杂度合理的好方法，而且二维线段树空间会爆。联想到数轴上的区间覆盖问题，我试着推广，但始终不能抓住要害，把二维的信息压缩到一维。数轴上的区间覆盖问题至少有两种方法，一是排序之后扫一遍，二是像差分数组一样+1、-1。

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 Atlan