Poj1151&HDU1542 Atlantis(扫描线+线段树)

时间:2022-12-25 19:18:02

题意

给定$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(扫描线+线段树)的更多相关文章

  1. &lbrack;POJ1151&rsqb;&lbrack;HDU1542&rsqb;Atlantis(线段树,扫描线)

    英文题面,我就只放个传送门了. Solution  题意是算矩形面积并,这是扫描线算法能解决的经典问题. 算法的大致思想是,把每一个矩形拆成上边和下边(以下称作扫描线),每条扫描线有四个参数l,r,h ...

  2. &lbrack;HDU1542&rsqb;Atlantis&lpar;扫描线&plus;线段树&rpar;

    Atlantis Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Su ...

  3. 【POJ1151】Atlantis(线段树,扫描线)

    [POJ1151]Atlantis(线段树,扫描线) 题面 Vjudge 题解 学一学扫描线 其实很简单啦 这道题目要求的就是若干矩形的面积和 把扫描线平行于某个轴扫过去(我选的平行\(y\)轴扫) ...

  4. hdu1542 Atlantis (线段树&plus;扫描线&plus;离散化)

    Atlantis Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total S ...

  5. poj1151 Atlantis——扫描线&plus;线段树

    题目:http://poj.org/problem?id=1151 经典的扫描线问题: 可以用线段树的每个点代表横向被矩形上下边分割开的每一格,这样将一个矩形的出现或消失化为线段树上的单点修改: 每个 ...

  6. hdu-1542 Atlantis&lpar;离散化&plus;线段树&plus;扫描线算法&rpar;

    题目链接: Atlantis Time Limit: 2000/1000 MS (Java/Others)     Memory Limit: 65536/32768 K (Java/Others) ...

  7. 【POJ1151】【扫描线&plus;线段树】Atlantis

    Description There are several ancient Greek texts that contain descriptions of the fabled island Atl ...

  8. POJ 1151 Atlantis &lpar;扫描线&plus;线段树&rpar;

    题目链接:http://poj.org/problem?id=1151 题意是平面上给你n个矩形,让你求矩形的面积并. 首先学一下什么是扫描线:http://www.cnblogs.com/scau2 ...

  9. hdu1542 Atlantis(扫描线&plus;线段树&plus;离散)矩形相交面积

    题目链接:点击打开链接 题目描写叙述:给定一些矩形,求这些矩形的总面积.假设有重叠.仅仅算一次 解题思路:扫描线+线段树+离散(代码从上往下扫描) 代码: #include<cstdio> ...

  10. HDU 3642 - Get The Treasury - &lbrack;加强版扫描线&plus;线段树&rsqb;

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3642 Time Limit: 10000/5000 MS (Java/Others) Memory L ...

随机推荐

  1. Windows10&plus;Ubuntu双系统安装 (转)

    1.Windows10+Ubuntu双系统安装:   http://www.jianshu.com/p/2eebd6ad284d 2.UEFI启动模式安装ubuntu指南  :  http://col ...

  2. js 获取时间比较全,留备用(zhuan)

    var myDate = new Date(); myDate.getYear();        //获取当前年份(2位) myDate.getFullYear();    //获取完整的年份(4位 ...

  3. 换行符在ajax中返回json,eval时发生的 Unexpected token ILLEGAL

    用户如果输入了换行在数据中记录为‘空格’,但不是真正的空格. 程序前台采用ajax和json返回数据绑定时会 出现 Unexpected token ILLEGAL 例子: 在sql中存储为下图 在“ ...

  4. Bootstrap里的文件分别表示什么?都有什么用?

    bootstrap.css 是完整的bootstrap样式表,未经压缩过的,可供开发的时候进行调试用bootstrap.min.css 是经过压缩后的bootstrap样式表,内容和bootstrap ...

  5. 章节十、7-Xpath---Xpath中绝对路径相对路径的区别

    以下演示操作以该网址中的内容为例:https://learn.letskodeit.com/?_ga=2.143454972.85111248.1555037144-697706367.1554889 ...

  6. dhtmlx Gantt知识点1

    鼠标放在任务上显示信息框: <script src="../../codebase/ext/dhtmlxgantt_tooltip.js?v=5.2.0"></s ...

  7. LockScreen

    <Window x:Class="XXX.Client.LockScreenView" xmlns="http://schemas.microsoft.com/wi ...

  8. Git Submodule管理项目子模块

    使用场景 当项目越来越庞大之后,不可避免的要拆分成多个子模块,我们希望各个子模块有独立的版本管理,并且由专门的人去维护,这时候我们就要用到git的submodule功能. 常用命令 git clone ...

  9. MySQL 数据库-索引注意事项

        索引注意事项 (1)最左前缀原则 如果查询的时候,查询条件精确匹配索引的左边连续一列或几列,则可以命中索引. (2)避免where 子句中对字段施加函数,如to_date(create_tim ...

  10. 《Python》re模块补充、异常处理

    一.re模块 1.match方法 import re # match 验证用户输入的内容 ret = re.match('\d+', 'hhoi2342ho12ioh11') print(ret) # ...