http://poj.org/problem?id=1151

经典矩形面积并吧.....很简单我就不说了...

有个很神的地方,我脑残没想到:

将线段变成点啊QAQ这样方便计算了啊

还有个很坑的地方,为毛每一次我精确地计算过空间可就是wa....一改大就ac...我无力了..

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define error(x) (!(x)?puts("error"):0)
#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; } const int N=1005;
#define lc x<<1
#define rc x<<1|1
#define lson l, mid, lc
#define rson mid+1, r, rc
int tot, idn;
double idy[N*2];
struct T { double sum; int num; }t[N*8+10];
void pushup(int x, int l, int r) { if(t[x].num>0) t[x].sum=idy[r+1]-idy[l]; else t[x].sum=t[lc].sum+t[rc].sum; }
void update(int L, int R, int k, int l=1, int r=tot, int x=1) {
if(L<=l && r<=R) { t[x].num+=k; pushup(x, l, r); return; }
int mid=(l+r)>>1;
if(L<=mid) update(L, R, k, lson);
if(mid<R) update(L, R, k, rson);
pushup(x, l, r);
}
int n, ln; struct dat { double x, y[2]; int flag; }line[N*2];
bool cmp(const dat &a, const dat &b) { return a.x<b.x; }
void cln() { tot=tot*4+1; rep(i, tot) t[i].sum=0, t[i].num=0; tot=0; } int main() {
int test=0;
while(read(n), n) {
ln=idn=tot=0;
for1(i, 1, n) {
static double x[2], y[2];
rep(k, 2) scanf("%lf%lf", &x[k], &y[k]), idy[++idn]=y[k];
++ln; line[ln].x=x[0]; rep(k, 2) line[ln].y[k]=y[k]; line[ln].flag=1;
++ln; line[ln].x=x[1]; rep(k, 2) line[ln].y[k]=y[k]; line[ln].flag=-1;
}
sort(idy+1, idy+1+idn);
idn=unique(idy+1, idy+1+idn)-idy-1;
tot=idn-1; sort(line+1, line+1+ln, cmp);
line[0].x=line[1].x;
double ans=0;
for1(i, 1, ln) {
ans+=t[1].sum*(line[i].x-line[i-1].x);
int left=lower_bound(idy+1, idy+1+idn, line[i].y[0])-idy,
rigt=lower_bound(idy+1, idy+1+idn, line[i].y[1])-idy-1;
update(left, rigt, line[i].flag);
} printf("Test case #%d\n", ++test);
printf("Total explored area: %.2f\n", ans);
puts("");
cln();
}
return 0;
}

  


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.

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.

Sample Input

2
10 10 20 20
15 15 25 25.5
0

Sample Output

Test case #1
Total explored area: 180.00

Source

最新文章

  1. 添加native service
  2. 配置移动前端开发调试环境(nodejs+npm+weiner的安装和配置使用)
  3. js 随笔
  4. AC自动机题目汇总
  5. RequiredFieldValidator 根据group组来触发验证
  6. mysql 源码调试方法
  7. perl 继承概述
  8. html bottom html submit按钮表单控件与CSS美化
  9. Dom的增删查改以及常用事件
  10. Tornado框架简介(二)
  11. bzoj 2109: [Noi2010]Plane 航空管制
  12. python装饰器1:函数装饰器详解
  13. Eclipse Todo Tasks 任务试图
  14. Collections.sort 的日期排序
  15. django模板语言循环字典,及forloop
  16. Mysql删除重复记录,保留id最小的一条
  17. django -- 美多订单分表
  18. flaks___git
  19. 【Direct2D1.1初探】Direct2D特效概览
  20. scala spark 调用hivecontext

热门文章

  1. javascript quine
  2. Python获取目录、文件的注意事项
  3. 隐藏Nginx/Apache版本号的安全性与方法
  4. Gson简要使用
  5. js 实现图片预加载 (js操作 Image对象属性complete ,事件onload 异步加载图片)
  6. MyBatis3: Could not find SQL statement to include with refid ‘
  7. iOS 和 Android 触摸事件传递
  8. Android Studio &quot;diamond operator is not supported&quot; 处理方法
  9. 转关于垂直切分Vertical Sharding的粒度
  10. Java for LeetCode 029 Divide Two Integers