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

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

Input输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.

注意:本题的输入数据较多,推荐使用scanf读入数据. 
Output对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数. 
Sample Input

2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1

Sample Output

7.63
0.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]; int times[MAXN<<];
double X[MAXN], one[MAXN], more[MAXN<<];
//X用于离散化横坐标,times为此区间被覆盖的次数,
//one为此区间被覆盖一次的长度和, more为此区间至少被覆盖两次的长度和 void push_up(int u, int l, int r)
{
if(times[u]>=) //该区间被覆盖了两次
{
more[u] = X[r] - X[l];
one[u] = X[r] - X[l];
}
else if(times[u]==) //该区间被覆盖了一次
{
more[u] = one[u*]+one[u*+];
one[u] = X[r] - X[l];
}
else //该区间没有被覆盖
{
if(l+==r) //该区间为单位区间
more[u] = one[u] = ;
else
{
more[u] = more[u*]+more[u*+];
one[u] = one[u*]+one[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 val)
{
if(x<=l && r<=y)
{
times[u] += val;
push_up(u, l, r);
return;
} int mid = (l+r)>>;
if(x<=mid-) add(u*, l, mid, x, y, val);
if(y>=mid+) add(u*+, mid, r, x, y, val);
push_up(u, l, r);
} int main()
{
int n, T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &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(more, , sizeof(more));
memset(one, , sizeof(one));
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 += more[]*(Line[i+].h-Line[i].h);
}
printf("%.2f\n", ans);
}
}

最新文章

  1. 50道java算法题(一)
  2. 主DNS配置
  3. [原创]Java静态代码检查工具介绍
  4. Python学习(1)
  5. LevelDB系列之SSTable(Sorted Strings Table)文件
  6. HDU 1372 Knight Moves【BFS】
  7. 使用GLSL实现的海洋效果 【转】
  8. mysql语句大全
  9. 做个无边框winform窗体,并美化界面
  10. JavaScript arguments类数组
  11. mybatis枚举映射成tinyint
  12. Android首选项SharedPreference-android学习之旅(六)
  13. input下拉框
  14. JAVA进阶1
  15. Delphi - 子窗体继承父窗体后如何显示父窗体上的控件
  16. 实现在当前的日期上加N天
  17. 批量启动application pool
  18. 随笔记:如何使用Python连接(/操作)Oracle数据库(Windows平台下)
  19. React 入门实例教程[阮一峰的网络日志] (分享)
  20. Redis集群入门

热门文章

  1. N个数求和(模拟)
  2. javascript 保护变量不被随意修改------优雅的编程
  3. 【BZOJ2982】combination(Lucas定理)
  4. ***js常用方法汇总(源自实际中的项目)
  5. http://www.ybtsoft.com/
  6. Docker+Drone做Java/Tomcat的CI服务
  7. CentOS 5 全功能服务器搭建
  8. Error Code: 2006 - MySQL 鏈嶅姟鍣ㄥ凡绂荤嚎
  9. VC++ 2010编译错误 fatal error C1189 error This file requires _WIN32_WINNT to be #defined at least
  10. Java第二次作业參考代码