【题目链接】

点击打开链接

【算法】

线段树扫描线

推荐一篇比较容易理解的线段树扫描线的文章 : 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 ; }

最新文章

  1. web开发调试神器——fiddler的使用
  2. Job for httpd.service failed because the control process exited with error code. See &quot;systemctl status httpd.service&quot; and &quot;journalctl -xe&quot; for details
  3. 1Z0-053 争议题目解析510
  4. 解决Window Azure: Failed to start Development Storage: the SQL Server instance ‘localhost\SQLExpress’ could not be found.
  5. uiscrollView UINavigation和uitabbar添加约束的问题
  6. PHP中的一个”坑“
  7. 分析函数调用关系图(call graph)的几种方法
  8. Webview的使用和注意事项
  9. linux c语言定时器
  10. Javascripte的原型链之基础讲解
  11. Spring发送邮件
  12. 【SQL触发器】类型 FOR 、AFTER、 Instead of
  13. 15Linux_DHCP_Postfix_Dovecot_LDAP
  14. 51nod 1238 最小公倍数之和 V3
  15. ES6 原始类型 Symbol
  16. C#XML注释
  17. 【转】ASP.NET Core API 版本控制
  18. UI5-文档-4.1-Hello World!
  19. Java线程和多线程(十三)——Callable,Future,FutureTask
  20. CentOS yum安装软件包

热门文章

  1. Codeforces Round #511 (Div. 2) C. Enlarge GCD
  2. spring data jpa 查询部分字段
  3. Vijos——1359 Superprime
  4. Atcoder 2373 Cookie Exchanges
  5. IntelliJ IDEA常用的快捷键(代码提示/注释代码/加入类注释和方法注释Javadoc)
  6. IntelliJ IDEA常用统一设置(Linux/Mac/Windows)
  7. [转] oracle里long类型的总结
  8. 【面试 spring】【第七篇】spring的问题
  9. pycharm、idea插件代理设置,插件安装
  10. Spring Boot 使用Java代码创建Bean并注冊到Spring中