【POJ 1151】 Altlantis
2024-08-30 13:18:54
【题目链接】
【算法】
线段树扫描线
推荐一篇比较容易理解的线段树扫描线的文章 : https://blog.csdn.net/u013480600/article/details/22548393
【代码】
注意此题输出格式若使用"%.2lf"会离奇Wrong Answer,要改为"%.2f"
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 110 int i,n,l1,l2,l,L,R,TC;
double xa,ya,xb,yb,area;
double a[MAXN*],x[MAXN*],arr[MAXN*]; struct info {
double l,r,h,opt;
} y[MAXN*]; struct SegmentTree {
struct Node {
int l,r,c;
double m;
} Tree[MAXN*];
inline void build(int index,int l,int r) {
int mid;
Tree[index].l = l;
Tree[index].r = r;
Tree[index].m = 0.0;
Tree[index].c = ;
if (l == r) return;
mid = (l + r) >> ;
build(index<<,l,mid);
build(index<<|,mid+,r);
}
inline void update(int index) {
if (Tree[index].c > ) Tree[index].m = arr[Tree[index].r+] - arr[Tree[index].l];
else if (Tree[index].l == Tree[index].r) Tree[index].m = ;
else Tree[index].m = Tree[index<<].m + Tree[index<<|].m;
}
inline void add(int index,int l,int r,int val) {
int mid;
if (Tree[index].l == l && Tree[index].r == r) {
Tree[index].c += val;
update(index);
return;
}
mid = (Tree[index].l + Tree[index].r) >> ;
if (mid >= r) add(index<<,l,r,val);
else if (mid + <= l) add(index<<|,l,r,val);
else {
add(index<<,l,mid,val);
add(index<<|,mid+,r,val);
}
update(index);
}
inline double query() {
return Tree[].m;
}
} T; bool cmp(info a,info b) { return a.h > b.h; } int main() { while (scanf("%d",&n) != EOF && n) {
l = l1 = l2 = ;
for (i = ; i <= n; i++) {
scanf("%lf%lf%lf%lf",&xa,&ya,&xb,&yb);
x[++l1] = xa;
x[++l1] = xb;
y[++l2] = (info){xa,xb,ya,-};
y[++l2] = (info){xa,xb,yb,};
}
sort(x+,x+l1+);
x[] = -;
for (i = ; i <= l1; i++) {
if (x[i] != x[i-])
arr[++l] = x[i];
}
T.build(,,l-);
sort(y+,y+l2+,cmp);
area = 0.0;
for (i = ; i < l2; i++) {
L = lower_bound(arr+,arr+l+,y[i].l) - arr;
R = lower_bound(arr+,arr+l+,y[i].r) - arr - ;
T.add(,L,R,y[i].opt);
area += T.query() * (y[i].h - y[i+].h);
}
printf("Test case #%d\nTotal explored area: %.2f\n\n",++TC,area);
} return ; }
最新文章
- web开发调试神器——fiddler的使用
- Job for httpd.service failed because the control process exited with error code. See ";systemctl status httpd.service"; and ";journalctl -xe"; for details
- 1Z0-053 争议题目解析510
- 解决Window Azure: Failed to start Development Storage: the SQL Server instance ‘localhost\SQLExpress’ could not be found.
- uiscrollView UINavigation和uitabbar添加约束的问题
- PHP中的一个”坑“
- 分析函数调用关系图(call graph)的几种方法
- Webview的使用和注意事项
- linux c语言定时器
- Javascripte的原型链之基础讲解
- Spring发送邮件
- 【SQL触发器】类型 FOR 、AFTER、 Instead of
- 15Linux_DHCP_Postfix_Dovecot_LDAP
- 51nod 1238 最小公倍数之和 V3
- ES6 原始类型 Symbol
- C#XML注释
- 【转】ASP.NET Core API 版本控制
- UI5-文档-4.1-Hello World!
- Java线程和多线程(十三)——Callable,Future,FutureTask
- CentOS yum安装软件包
热门文章
- Codeforces Round #511 (Div. 2) C. Enlarge GCD
- spring data jpa 查询部分字段
- Vijos——1359 Superprime
- Atcoder 2373 Cookie Exchanges
- IntelliJ IDEA常用的快捷键(代码提示/注释代码/加入类注释和方法注释Javadoc)
- IntelliJ IDEA常用统一设置(Linux/Mac/Windows)
- [转] oracle里long类型的总结
- 【面试 spring】【第七篇】spring的问题
- pycharm、idea插件代理设置,插件安装
- Spring Boot 使用Java代码创建Bean并注冊到Spring中