题意:求矩形周长并。
总结:这道题也算是很经典的一道扫描线题吧,就是陈宏论文上面提到的那道IOI的试题,也算试了一下用扫描线法求矩形的周长并.
注意点:1.几个必须要的域,cnt-区间被线段覆盖的次数,sum-测度,seq-连续段数,lbd-是否包含区间的左边界,rbd-是否包含区间的右边界,其中lbd,rbd是为了求得seq的。
2.理解线段插入删除的思想。//为什么在这里不需要把信息传给子节点,这里需要进一步理解。
3.理解如果更新上述的几个域.
4.如何根据测度信息和连续段数信息计算答案。//需要进一步理解
各种蛋疼:1.注意求X方向的周长与求Y方向的周长位于update的两侧。。(细想一下就知道了)
网上讲这个题的资料很多(强烈推荐1999年陈宏的国家集训队论文),不多说了,直接上代码。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN = 5555;
double sum[MAXN*6],x[MAXN*2];
int cnt[MAXN*6],rbd[MAXN*6],lbd[MAXN*6],seq[MAXN*6],n,num_x,line_num;
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];
#define lson l,m,rt<<1
#define rson m,r,rt<<1|1
void pushUP(int l,int r,int rt){
if(cnt[rt]){
sum[rt] = x[r]-x[l];
seq[rt] = lbd[rt] = rbd[rt] = 1;
}else{
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
seq[rt] = seq[rt<<1]+seq[rt<<1|1]-rbd[rt<<1]*lbd[rt<<1|1];
rbd[rt] = rbd[rt<<1|1];
lbd[rt] = lbd[rt<<1];
}
}
void update(int L,int R,int s,int l,int r,int rt){
if(L<=l&&R>=r){
cnt[rt]+=s;
pushUP(l,r,rt);
//cout<<l<<" "<<r<<" "<<seq[rt]<<" "<<lbd[rt]<<" "<<rbd[rt]<<endl;system("pause");
return;
}
int m = (l+r)>>1;
if(m>L)update(L,R,s,lson);
if(m<R)update(L,R,s,rson);
pushUP(l,r,rt);
//cout<<l<<" "<<r<<" "<<seq[rt]<<" "<<lbd[rt]<<" "<<rbd[rt]<<endl;system("pause");
}
int search(double k){
int l=0,r=num_x-1,m;
while(l<=r){
m = (l+r)>>1;
if(x[m]==k)return m;
else if(k<x[m])r=m-1;
else l=m+1;
}
return -1;
}
int main(){
while(scanf("%d",&n)!=EOF){
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(L,L+line_num);sort(x,x+num_x);
int temp = 1;
for(int i=1;i<num_x;i++)if(x[i]!=x[i-1])x[temp++]=x[i];
num_x = temp;
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
memset(seq,0,sizeof(seq));
memset(lbd,0,sizeof(lbd));
memset(rbd,0,sizeof(rbd));
double ans = 0,preM = 0;
for(int i=0;i<line_num;i++){
int l = search(L[i].l);
int r = search(L[i].r);
if(i)ans += 2*seq[1]*(L[i].h-L[i-1].h);
update(l,r,L[i].s,0,num_x-1,1);
//cout<<l<<" "<<r<<" "<<L[i].h<<" "<<L[i].s<<endl;
//cout<<sum[1]<<" "<<seq[1]<<" "<<lbd[1]<<" "<<rbd[1]<<endl;
ans += fabs(sum[1]-preM);
preM = sum[1];
}
printf("%.0lf\n",ans);
}
return 0;
}
分享到:
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
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题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
poj 3310 的代码和方法说明,个人原创
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。