/*
线段树+扫描线+离散化
求多个矩形的面积
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
using namespace std;
const int maxn = 105;
const int maxm = 210;
struct SegTree{
int l,r;
int cover;
double L_val,R_val;
double sum;
}ST[ maxm<<2 ];
struct Line{
double x,y1,y2;
bool InOut;
}yLine[ maxm ];
int cmp( Line a,Line b ){
return a.x<b.x;
}
double yIndex[ maxm ];
int GetIndex( double val,int cnt ){
return lower_bound( yIndex,yIndex+cnt,val )-yIndex;
}
void build( int L,int R,int n ){
ST[ n ].l = L;
ST[ n ].r = R;
ST[ n ].cover = 0;
ST[ n ].sum = 0;
ST[ n ].L_val = yIndex[ L ];
ST[ n ].R_val = yIndex[ R ];
if( R-L>1 ){
int mid = (L+R)/2;
build( L,mid,2*n );
build( mid,R,2*n+1 );
}
}
void PushUp( int n ){
if( ST[ n ].cover>0 ){
ST[ n ].sum = ST[ n ].R_val-ST[ n ].L_val;
}
else if( ST[ n ].r-ST[ n ].l>1 ){
ST[ n ].sum = ST[ 2*n ].sum+ST[ 2*n+1 ].sum;
}
else
ST[ n ].sum = 0;
}
void update( int left,int right,bool InOut,int n ){
if( left==ST[ n ].l&&right==ST[ n ].r ){
if( InOut==true ){
ST[ n ].cover++;
}
else{
ST[ n ].cover--;
}
}
else {
int mid = (ST[ n ].l+ST[ n ].r)/2;
if( mid>=right ) update( left,right,InOut,2*n );
else if( mid<=left ) update( left,right,InOut,2*n+1 );
else {
update( left,mid,InOut,2*n );
update( mid,right,InOut,2*n+1 );
}
}
PushUp( n );
}
int main(){
int n;
int T = 1;
while( scanf("%d",&n)==1,n ){
printf("Test case #%d\n",T++);
double x1,y1,x2,y2;
int cnt = 0;
for( int i=0;i<n;i++ ){
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
yLine[ 2*i ].x = x1;
yLine[ 2*i+1 ].x = x2;
yLine[ 2*i ].y1 = yLine[ 2*i+1 ].y1 = y1;
yLine[ 2*i ].y2 = yLine[ 2*i+1 ].y2 = y2;
yLine[ 2*i ].InOut = true;
yLine[ 2*i+1 ].InOut = false;
yIndex[ 2*i ] = y1;
yIndex[ 2*i+1 ] = y2;
}
sort( yLine,yLine+2*n,cmp );
sort( yIndex,yIndex+2*n );
for( int i=1;i<2*n;i++ ){
if( yIndex[i]!=yIndex[i-1] )
yIndex[ cnt++ ] = yIndex[ i-1 ];
}
yIndex[ cnt++ ] = yIndex[ 2*n-1 ];
build( 0,cnt-1,1 );
double res = 0;
update( GetIndex( yLine[0].y1,cnt ),GetIndex( yLine[0].y2,cnt ),yLine[0].InOut,1 );
for( int i=1;i<2*n;i++ ){
res += ST[ 1 ].sum*( yLine[i].x-yLine[i-1].x );
update( GetIndex( yLine[i].y1,cnt ),GetIndex( yLine[i].y2,cnt ),yLine[i].InOut,1 );
}
printf("Total explored area: %.2lf\n\n",res);
}
return 0;
}
分享到:
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
线段树、树状数组算法入门 加 poj解题报告 pdf文档
POJ3468,线段树处理,注意longlongint
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1746750
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
北大POJ初级-简单搜索 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://200830740306.iteye.com/blog/603493
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码