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 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.
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
C++版本一
#include <iostream>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
const int N=10000+10;
int t,n,cnt=0;
double x,x2,y,y2;
double tree[N];
int flag[N];
double X[N];
void init(){
memset(tree,0,sizeof(tree));
memset(flag,0,sizeof(flag));
cnt=0;
}
struct node{
double l,r,y;
int s;
node(){};
node(double l0,double r0,double y0,double s0){
l=l0;
r=r0;
y=y0;
s=s0;
}
bool operator <(const node &S)const{
return y<S.y;
}
}G[N];
void pushup(int i,int l,int r){
if(flag[i])
tree[i]=X[r+1]-X[l];
else if(l==r)
tree[i]=0;
else
tree[i]=tree[i<<1]+tree[i<<1|1];
}
void updata(int i,int l, int r,int L,int R,int C){
if(L<=l&&r<=R){
flag[i]+=C;
pushup(i,l,r);
return;
}
int m=(l+r)>>1;
if(R<=m)
updata(i<<1,l,m,L,R,C);
else if(L>m)
updata(i<<1|1,m+1,r,L,R,C);
else{
updata(i<<1,l,m,L,m,C);
updata(i<<1|1,m+1,r,m+1,R,C);
}
pushup(i,l,r);
}
int main()
{ t=1;
while(scanf("%d",&n)!=EOF){
if(n==0) break;
init();
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&x,&y,&x2,&y2);
G[++cnt]=node(x,x2,y,1);
X[cnt]=x;
G[++cnt]=node(x,x2,y2,-1);
X[cnt]=x2;
}
sort(X+1,X+cnt+1);
sort(G+1,G+cnt+1);
int k=1;
for(int i=2;i<=cnt;i++)
if(X[i]!=X[i+1])
X[++k]=X[i];
double ans=0;
for(int i=1;i<cnt;i++){
int l=lower_bound(X+1,X+k+1,G[i].l)-X;
int r=lower_bound(X+1,X+k+1,G[i].r)-X-1;
updata(1,1,k,l,r,G[i].s);
ans+=tree[1]*(G[i+1].y-G[i].y);
}
printf("Test case #%d\n",t++);
printf("Total explored area: %.2f\n\n",ans+0.0001);
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
线段树扫描线又是线段树的一种特殊的跑法
先将X坐标离散化
然后将扫描线按照高度从矮到高进行更新
每次遇到下边的时候就在对应的左区间右区间所对应的cnt值++
每次遇到上边的时候就在对应的左区间右区间所对应的cnt值--
然后在PushUp 如果 cnt>0 那么说明整个区间内的线都是有效的 这个时候只需要计算整个区间的长度
如果cnt == 0 并且 l == r 那么就说明这个区间内是没有有效的线
如果cnt == 0 并且 l != r 那么这个区间内的有效线段就是下属区间的有效线段之和
至于访问到下面的时候为什么不需要将cnt标记下推
原因有2个: 1.无论下边的节点是2 还是3 只要这个节点的cnt>0 那么就是整个区间的线段都是有效线段 所以不需要具体到将cnt标记下推来区分左子叶的cnt值是1 右节点的cnt值是2 还是3， 效果都是一样的。
2：因为每一条下边长的扫描线都会有一条完全对应的上变成的扫描线来抵消 所以 这个影响会在后面抵消。
最后每次跑扫描线的时候只需要将 sum[1]*（高度差）累加起来就是答案了。
https://www.cnblogs.com/MingSD/p/8392240.html
#include<iostream>
#include<algorithm>
#include<iomanip>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int N = 1e3;
struct Node
{
double l, r, h;
int d;
bool operator < (const Node & x) const
{
return h < x.h;
}
}A[N];
double X[N], sum[N];
int cnt[N];
void Build(int l, int r, int rt)
{
cnt[rt] = 0, sum[rt] = 0.0;
if(l == r) return ;
int m = l+r >> 1;
Build(lson);
Build(rson);
}
void PushUp(int l, int r, int rt)
{
if(cnt[rt])
{
sum[rt] = X[r] - X[l-1];
}
else if(l == r) sum[rt] = 0.0;
else sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void Revise(int L, int R, int C, int l, int r, int rt)
{
if(L <= l && r <= R)
{
cnt[rt] += C;
PushUp(l,r,rt);
return ;
}
int m = l+r >> 1;
if(L <= m) Revise(L,R,C,lson);
if(m < R) Revise(L,R,C,rson);
PushUp(l,r,rt);
}
void Add(double l, double r, double h, int d, int i)
{
A[i].l = l; A[i].h = h;
A[i].r = r; A[i].d = d;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int Case = 0, n;
while(cin >> n, n)
{
int k = 0;
double x1, y1, x2, y2;
for(int i = 1; i <= n; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
Add(x1,x2,y1,1,k);
X[k++] = x1;
Add(x1,x2,y2,-1,k);
X[k++] = x2;
}
sort(X,X+k);
sort(A,A+k);
int pos = 1;
for(int i = 1; i < k; i++)
{
if(X[i] != X[i-1])
X[pos++] = X[i];
}
Build(1,pos,1);
double ans = 0;
for(int i = 0; i < k-1; i++)
{
int l = lower_bound(X,X+pos,A[i].l) - X;
int r = lower_bound(X,X+pos,A[i].r) - X;
Revise(l+1,r,A[i].d,1,pos,1);
ans += (A[i+1].h - A[i].h) * sum[1];
}
cout << "Test case #" << ++Case << endl;
cout << "Total explored area: " << fixed
<< setprecision(2) << ans << endl << endl;
}
return 0;
}
京公网安备 11010502036488号