题意
给定$n$个矩形$(x_1,y_1,x_2,y_2)$,求这$n$个矩形的面积并
题解
扫描线裸题,可以不用线段树维护,$O(n^2)$是允许的。
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::sort;
using std::unique;
using std::lower_bound;
const int N = 1e2 + 10;
int n, m, tot;
double ans, x1[N], y1[N], x2[N], y2[N], raw[N << 1], tmp[N << 1];
struct Node {
double x, dy, uy, g;
inline bool operator < (const Node &a) const { return x < a.x; }
} cy[N << 1]; int cnt;
double val[N << 3]; int fg[N << 3];
inline void update(int o, int l, int r) {
if(fg[o]) val[o] = raw[r + 1] - raw[l];
else if(l == r) val[o] = 0;
else val[o] = val[o << 1] + val[o << 1 | 1];
}
void modify (int ml, int mr, int k, int o = 1, int l = 1, int r = m) {
if(l >= ml && r <= mr) {
fg[o] += k, update(o, l, r);
return ;
}
int mid = (l + r) >> 1, lc = o << 1, rc = lc | 1;
if(ml <= mid) modify(ml, mr, k, lc, l, mid);
if(mr > mid) modify(ml, mr, k, rc, mid + 1, r);
update(o, l, r);
}
int main () {
while(scanf("%d", &n) != EOF) {
if(!n) break; ++tot; ans = m = cnt = 0;
memset(val, 0, sizeof val), memset(fg, 0, sizeof fg);
for(int i = 1; i <= n; ++i) {
scanf("%lf%lf%lf%lf", x1 + i, y1 + i, x2 + i, y2 + i);
tmp[++m] = y1[i], tmp[++m] = y2[i];
}
sort(&tmp[1], &tmp[m + 1]); m = unique(&tmp[1], &tmp[m + 1]) - tmp - 1;
for(int i = 1; i <= n; ++i) {
int ind1 = lower_bound(&tmp[1], &tmp[m + 1], y1[i]) - tmp;
int ind2 = lower_bound(&tmp[1], &tmp[m + 1], y2[i]) - tmp;
raw[ind1] = y1[i], raw[ind2] = y2[i], y1[i] = ind1, y2[i] = ind2;
}
for(int i = 1; i <= n; ++i) {
cy[++cnt] = (Node){x1[i], y1[i], y2[i], 1};
cy[++cnt] = (Node){x2[i], y1[i], y2[i], -1};
} sort(&cy[1], &cy[cnt + 1]);
for(int i = 1; i <= cnt; ++i) {
modify(cy[i].dy, cy[i].uy - 1, cy[i].g);
ans += val[1] * (cy[i + 1].x - cy[i].x);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n", tot, ans);
}
return 0;
}
Poj1151&HDU1542 Atlantis(扫描线+线段树)的更多相关文章
-
[POJ1151][HDU1542]Atlantis(线段树,扫描线)
英文题面,我就只放个传送门了. Solution 题意是算矩形面积并,这是扫描线算法能解决的经典问题. 算法的大致思想是,把每一个矩形拆成上边和下边(以下称作扫描线),每条扫描线有四个参数l,r,h ...
-
[HDU1542]Atlantis(扫描线+线段树)
Atlantis Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Su ...
-
【POJ1151】Atlantis(线段树,扫描线)
[POJ1151]Atlantis(线段树,扫描线) 题面 Vjudge 题解 学一学扫描线 其实很简单啦 这道题目要求的就是若干矩形的面积和 把扫描线平行于某个轴扫过去(我选的平行\(y\)轴扫) ...
-
hdu1542 Atlantis (线段树+扫描线+离散化)
Atlantis Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total S ...
-
poj1151 Atlantis——扫描线+线段树
题目:http://poj.org/problem?id=1151 经典的扫描线问题: 可以用线段树的每个点代表横向被矩形上下边分割开的每一格,这样将一个矩形的出现或消失化为线段树上的单点修改: 每个 ...
-
hdu-1542 Atlantis(离散化+线段树+扫描线算法)
题目链接: Atlantis Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) ...
-
【POJ1151】【扫描线+线段树】Atlantis
Description There are several ancient Greek texts that contain descriptions of the fabled island Atl ...
-
POJ 1151 Atlantis (扫描线+线段树)
题目链接:http://poj.org/problem?id=1151 题意是平面上给你n个矩形,让你求矩形的面积并. 首先学一下什么是扫描线:http://www.cnblogs.com/scau2 ...
-
hdu1542 Atlantis(扫描线+线段树+离散)矩形相交面积
题目链接:点击打开链接 题目描写叙述:给定一些矩形,求这些矩形的总面积.假设有重叠.仅仅算一次 解题思路:扫描线+线段树+离散(代码从上往下扫描) 代码: #include<cstdio> ...
-
HDU 3642 - Get The Treasury - [加强版扫描线+线段树]
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3642 Time Limit: 10000/5000 MS (Java/Others) Memory L ...
随机推荐
-
Windows10+Ubuntu双系统安装 (转)
1.Windows10+Ubuntu双系统安装: http://www.jianshu.com/p/2eebd6ad284d 2.UEFI启动模式安装ubuntu指南 : http://col ...
-
js 获取时间比较全,留备用(zhuan)
var myDate = new Date(); myDate.getYear(); //获取当前年份(2位) myDate.getFullYear(); //获取完整的年份(4位 ...
-
换行符在ajax中返回json,eval时发生的 Unexpected token ILLEGAL
用户如果输入了换行在数据中记录为‘空格’,但不是真正的空格. 程序前台采用ajax和json返回数据绑定时会 出现 Unexpected token ILLEGAL 例子: 在sql中存储为下图 在“ ...
-
Bootstrap里的文件分别表示什么?都有什么用?
bootstrap.css 是完整的bootstrap样式表,未经压缩过的,可供开发的时候进行调试用bootstrap.min.css 是经过压缩后的bootstrap样式表,内容和bootstrap ...
-
章节十、7-Xpath---Xpath中绝对路径相对路径的区别
以下演示操作以该网址中的内容为例:https://learn.letskodeit.com/?_ga=2.143454972.85111248.1555037144-697706367.1554889 ...
-
dhtmlx Gantt知识点1
鼠标放在任务上显示信息框: <script src="../../codebase/ext/dhtmlxgantt_tooltip.js?v=5.2.0"></s ...
-
LockScreen
<Window x:Class="XXX.Client.LockScreenView" xmlns="http://schemas.microsoft.com/wi ...
-
Git Submodule管理项目子模块
使用场景 当项目越来越庞大之后,不可避免的要拆分成多个子模块,我们希望各个子模块有独立的版本管理,并且由专门的人去维护,这时候我们就要用到git的submodule功能. 常用命令 git clone ...
-
MySQL 数据库-索引注意事项
索引注意事项 (1)最左前缀原则 如果查询的时候,查询条件精确匹配索引的左边连续一列或几列,则可以命中索引. (2)避免where 子句中对字段施加函数,如to_date(create_tim ...
-
《Python》re模块补充、异常处理
一.re模块 1.match方法 import re # match 验证用户输入的内容 ret = re.match('\d+', 'hhoi2342ho12ioh11') print(ret) # ...