Atlantis
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 16991 | Accepted: 6479 |
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.
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.
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
题意:
给出 N (1 ~ 100),代表有 N 个矩形,后给出 N 个矩形的左下坐标值和右上坐标值,输出所有矩形所覆盖的面积和,面积和输出两位小数。直到输出 N = 0 结束。
思路:
线段树 + 扫描线 + 离散化。过程和求周长和类似,但是面积和就更简单了,不用保存覆盖的端点个数和区间左右端点的覆盖情况,因为面积完全只由长和宽决定,所以维护覆盖的长度和就好,并且统计的时候不用记录上一次的长度值,每次查询后再插入就行了。记得长度是浮点型的。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int MAX = 200000; typedef struct { double x, y1, y2; int temp; } node; node line[105 * 2]; double yy[105 * 2]; double len[MAX * 3]; int cover[MAX * 3]; bool cmp(node a, node b) { if (a.x != b.x) return a.x < b.x; return a.temp > b.temp; } void push_up(int node, int l, int r) { if (cover[node]) len[node] = yy[r] - yy[l]; else if (r - l == 1) len[node] = 0; else len[node] = len[node << 1] + len[node << 1 | 1]; } void build (int node, int l, int r) { if (r - l == 1) { len[node] = 0; } else { int mid = (r + l) >> 1; build(node << 1, l, mid); build(node << 1 | 1, mid, r); push_up(node, l, r); } } void updata (int node, int l, int r, int cl, int cr, int c) { if (cl > r || cr < l) return; if (cl <= l && cr >= r) { cover[node] += c; push_up(node, l, r); return; } if (r - l == 1) return; int mid = (r + l) >> 1; updata(node << 1, l, mid, cl, cr, c); updata(node << 1 | 1, mid, r, cl, cr, c); push_up(node, l, r); } int main() { int n, t = 0; while (~scanf("%d", &n) && n) { int ans = 0, m = 0; while (n--) { double x1, y1, x2, y2; scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); line[ans].x = x1; line[ans].y1 = y1; line[ans].y2 = y2; line[ans++].temp = 1; line[ans].x = x2; line[ans].y1 = y1; line[ans].y2 = y2; line[ans++].temp = -1; yy[m++] = y1; yy[m++] = y2; } sort(yy, yy + m); m = unique(yy, yy + m) - yy; sort(line, line + ans, cmp); build(1, 0, ans - 1); double res = 0; for (int i = 0; i < ans; ++i) { int ll = lower_bound(yy, yy + m, line[i].y1) - yy; int rr = lower_bound(yy, yy + m, line[i].y2) - yy; if (i) { double x, y; x = line[i].x - line[i - 1].x; y = len[1]; res += x * y; } updata(1, 0, ans - 1, ll, rr, line[i].temp); } printf("Test case #%d\n", ++t); printf("Total explored area: %.2lf\n\n", res); } return 0; }
相关推荐
Atlantis 线段树 离散化 解题报告
Atlantis
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
Atlantis - 一个DDD+CQS+Grpc+RabbitMQ的快速开发框架 框架采用了 DDD 理论模型开发,其中分C端(写端)和Q端(读端)两个部分。C端使用DDD,Q端直接使用数据库,其目的是为了严谨对写的操作,而Q端作为查询需要快速...
Atlantis Word Processor是一款简单好用的文字处理软件。软件功能强大,支持读取并编辑*.rtf *.doc *.docx *.cod *.txt等数种格式的文档,支持命令行,,并且软件的界面可以按照你的意愿自定义。Atlantis Word ...
非常著名的消消樂遊戲,遊戲畫面精緻華麗,關卡多,難度會依過關次數依序增加,內含破解檔,安裝後將破解檔直接覆蓋原檔案即可。
Atlantis mf
是用于Terraform拉取请求自动化的强大工具。 每个仓库都可以有一个YAML配置文件,该文件定义了Terraform模块的依赖关系,因此影响依赖模块的PR将自动为这些模块生成Terraform terraform plan 。 是一个Terraform...
Atlantis Lite(深色设计)是一个免费的bootstrap 4管理仪表盘,其设计精美,美观,可以显示各种指标,数字或数据可视化。 Atlantis Lite管理仪表盘具有2种布局,许多插件和UI组件,可帮助开发人员快速有效地创建...
Terras-aws-ecs-atlantis 用于将部署到AWS ECS集群的Terraform模块。 该项目是我们针对DevOps的全面方法的一部分。 它是100%开源的,并根据许可。 从字面上看,我们有,它们都是开源的并且维护良好。 去看一下...
Atlantis Lite是一个免费的bootstrap 4管理仪表盘,其设计精美,优雅,可以显示各种指标,数字或数据可视化。 Atlantis Lite管理仪表盘具有2种布局,许多插件和UI组件,可帮助开发人员快速有效地创建仪表盘,从而...
terraform-aws-atlantis:用于在AWS Fargate上运行Atlantis的Terraform配置。 支持Github,Gitlab和BitBucket
Atlantis Lite管理仪表盘具有2种布局,许多插件和UI组件,可帮助开发人员快速有效地创建仪表盘,从而节省了开发时间,并帮助用户根据现有数据做出正确,快速的决策。 产品特点 DBMS:SQLite,PostgreSQL(生产) ...
用于Garry Mod的Stargate Atlantis模型和材料可支持sb_atlantis(Spacebuild 3的SGA地图)的开发。
Atlantis Talker是基于telnet的聊天服务器,具有留言板,邮件系统,游戏和房间等功能,所有功能均采用纯ASCII。 它主要用斯洛伐克语编写。
谈话者Atlantis的高级客户端的通信协议(现在在atlantis.talker.sk运行)。 没有执行。 没有源代码。 仅规范。
Atlantis 可以在路由请求中轻松的构建和部署应用到容器。Atlantis 在 Ooyala 的新应用中得到了很广泛的应用。Atlantis 开源库包括所有的组件,共享数据类型,通用函数。Atlantis 官方入门指南:...
Atlantis Lite是一个免费的bootstrap 4管理仪表盘,其设计精美,优雅,可以显示各种指标,数字或数据可视化。 Atlantis Lite管理仪表盘具有2种布局,许多插件和UI组件,可帮助开发人员快速有效地创建仪表盘,从而...