题意:求矩形面积并
前天直接用“矩形切割”(我也不知道我那方法是不是矩形切割,姑且打上引号吧),过掉了这个题,那个猥琐的算法达到了O(n^3),如果题目数据很大的话,还是不行的,所以这两天还是继续学习扫描线,发现网上的很多文章讲的都不算很清楚,于是翻除了1999年陈宏的论文,开始研究,最终总算搞定了扫描线这个玩意儿。
注意点:要理解论文中提到的测度(即线段并的长度)和连续段的含义(求矩形周长并需要用到),这两点很关键,然后建树的时候用段树比较好一点,用点树我还没想到这么处理,建段树的话,数组稍微开大点(最好是5倍左右),否则会悲剧的。。
各种蛋疼:最后忘记去掉freopen..WA数次,蛋碎。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 5555;
struct Line{
double l,r,h;
int s;
Line(){}
Line(double ll,double rr,double hh,int ss):l(ll),r(rr),h(hh),s(ss){}
bool operator < (const Line &l) const {
return h<l.h;
}
}L[MAXN<<2];
double X[MAXN<<2],sum[MAXN<<2];
int cnt[MAXN<<2],num_x,n,line_num;
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
void pushUP(int rt,int l,int r){
if(cnt[rt]){
sum[rt] = X[r]-X[l];
}else{
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
}
void update(int L,int R,int s,int l,int r,int rt){
if(L<=l&&R>=r){
cnt[rt]+=s;
pushUP(rt,l,r);
return;
}
//cout<<L<<" "<<R<<" "<<l<<" "<<r<<endl;system("pause");
int m = (l+r)>>1;
if(m>L)update(L,R,s,lson);
if(m<R)update(L,R,s,rson);
pushUP(rt,l,r);
}
int search(double a[],double k){
int l=0,r=num_x-1,m;
while(l<=r){
m = (l+r)>>1;
if(a[m]==k)return m;
else if(k<a[m])r=m-1;
else l=m+1;
}
return -1;
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int cas=0;
while(scanf("%d",&n),n){
num_x = line_num = 0;
for(int i=0;i<n;i++){
double a,b,c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
X[num_x++] = a;
X[num_x++] = c;
L[line_num++] = Line(a,c,b,1);
L[line_num++] = Line(a,c,d,-1);
}
sort(X,X+num_x);
sort(L,L+line_num);
int size = 1;
for(int i=1;i<num_x;i++)if(X[i]!=X[i-1])X[size++]=X[i];
num_x = size;
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
double ans = 0;
int l,r;
l = search(X,L[0].l);
r = search(X,L[0].r);
update(l,r,L[0].s,0,num_x-1,1);
for(int i=1;i<line_num;i++){
ans+=sum[1]*(L[i].h-L[i-1].h);
l = search(X,L[i].l);
r = search(X,L[i].r);
update(l,r,L[i].s,0,num_x-1,1);
}
printf("Test case #%d\nTotal explored area: %.2lf\n\n",++cas,ans);
}
return 0;
}
分享到:
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
2遍dp poj_3613解题报告 poj_3613解题报告
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
POJ 3131 双向BFS解立体八数码问题
O(nlogn)凸包问题 poj2187
poj两道题的c++实现。已经测试过可以通过oj
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
poj 3310 的代码和方法说明,个人原创
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。