题目链接:https://vjudge.net/problem/HDU-1542

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. 

InputThe input file 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.OutputFor 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. 
Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00

代码如下:

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 1e5+; struct line
{
double le, ri, h;
int id;
bool operator<(const line &a)const{
return h<a.h;
}
}Line[MAXN]; //X用于离散化横坐标,times为此区间被覆盖的次数,sum为此区间被覆盖的长度
double X[MAXN], times[MAXN<<], sum[MAXN<<]; void push_up(int u, int l, int r)
{
if(times[u]>) //该区间被覆盖,则覆盖长度为区间长度
sum[u] = X[r] - X[l];
else //该区间没有被覆盖,如果为单位区间,则覆盖长度为0,否则为两个子区间的覆盖长度之和。
sum[u] = (l+==r)?:sum[u*]+sum[u*+];
} //此种线段树的操作对象为连续型,即最小的元素为长度为1的区间[l,r],其中l和r只代表端点(r-l>=1),用于确定
//区间的位置和长度,l和r本身没有特别的含义。而以往做的什么单点更新之类的,都属于离散型,在l处和r处是有含义的
void add(int u, int l, int r, int x, int y, int v)
{
if(x<=l && r<=y)
{
times[u] += v;
push_up(u, l, r);
return;
} int mid = (l+r)>>;
if(x<=mid-) add(u*, l, mid, x, y, v);
if(y>=mid+) add(u*+, mid, r, x, y, v);
push_up(u, l, r);
} int main()
{
int n, kase = ;
while(scanf("%d", &n) && n)
{
for(int i = ; i<=n; i++)
{
double x1, y1, x2, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
Line[i].le = Line[i+n].le = x1;
Line[i].ri = Line[i+n].ri = x2;
Line[i].h = y1; Line[i+n].h = y2;
Line[i].id = ; Line[i+n].id = -;
X[i] = x1; X[i+n] = x2;
} sort(Line+, Line++*n);
sort(X+, X++*n);
int m = unique(X+, X++*n) - (X+); //去重 memset(sum, , sizeof(sum));
memset(times, , sizeof(times)); double ans = ;
for(int i = ; i<=*n-; i++)
{
int l = upper_bound(X+, X++m, Line[i].le) - (X+);
int r = upper_bound(X+, X++m, Line[i].ri) - (X+);
add(, , m, l, r, Line[i].id);
ans += sum[]* (Line[i+].h-Line[i].h);
}
printf("Test case #%d\n", ++kase);
printf("Total explored area: %.2f\n\n", ans);
}
}

最新文章

  1. VMWare Tools 和 Shared folder(共享文件夹)
  2. new 一个button 然后dispose,最后这个button是null吗???
  3. ES6新特性:Javascript中的Reflect对象
  4. hdu 4006 The kth great number (优先队列)
  5. Could not create the view: An unexpected exception was thrown.如何解决
  6. 何时使用 Em 与 Rem
  7. ruby特性
  8. iOS中菊花。。。
  9. java提高篇(四)-----抽象类与接口
  10. python数字转字符串
  11. 简单理解Vue中的nextTick
  12. C++ Primer 笔记——顺序容器
  13. Java学习笔记44(多线程一:Thread类)
  14. 爽爽的GSON解析
  15. 【Java】包,jar包的扫描
  16. Vue模板 script部分
  17. easy_install与pip 区别
  18. MCS-51与8086指令系统比较
  19. todolist增加markdown模块
  20. Confluence 6 使用 LDAP 授权连接一个内部目录 - 用户组 Schema 设置

热门文章

  1. tcpcopy简单用法
  2. InnoDB透明页压缩与稀疏文件
  3. 跟初学者学习IbatisNet第二篇
  4. ssm依赖
  5. AR+ 实时音视频通话,虚拟与现实无缝结合
  6. bzoj 1503[NOI 2004] 郁闷的出纳员
  7. 【bzoj1090】 [SCOI2003]字符串折叠
  8. BZOJ 2308 莫队入门经典
  9. .net core webapi jwt 更为清爽的认证 ,续期很简单(2)
  10. 【C++基础 02】深拷贝和浅拷贝