POJ1151 Atlantis 线段树扫描线
2024-09-14 08:47:51
扫描线终于看懂了。。。咕咕了快三个月$qwq$
对于所有的横线按纵坐标排序,矩阵靠下的线权值设为$1$,靠上的线权值设为$-1$,然后执行线段树区间加减,每次的贡献就是有效宽度乘上两次计算时的纵坐标之差。
$cnt$数组记录每个位置被覆盖的次数,$sum$数组用来记区间总长度(即有效宽度),所以每一次把$sum[1]$乘上高就行了。
注意到每个$r$都减了$1$,原因是原先的坐标是点的坐标,而现在一个位置代表一个区间。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ls (tr<<1)
#define rs (tr<<1|1)
#define ull unsigned long long
#define ll long long
#define R register int
using namespace std;
namespace Fread {
static char B[<<],*S=B,*D=B;
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return ch<=||ch>=;}
inline void gs(char* s) {register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar()));}
}using Fread::g; using Fread::gs;
const int N=;
struct ln {
double l,r,x; int w; ln() {}
ln(double Ll,double rr,double xx,int ww) {l=Ll,r=rr,x=xx,w=ww;}
bool operator < (const ln& that) const {return x<that.x;}
}L[N]; int n,t,tot; double d[N];
int cnt[N<<]; double sum[N<<];
inline void upd(int tr,int l,int r) {
if(cnt[tr]) sum[tr]=d[r+]-d[l];
else if(l==r) sum[tr]=;
else sum[tr]=sum[ls]+sum[rs];
}
inline void change(int tr,int l,int r,int LL,int RR,int vl) {
if(LL<=l&&r<=RR) {cnt[tr]+=vl; upd(tr,l,r); return ;} R md=l+r>>;
if(LL<=md) change(ls,l,md,LL,RR,vl); if(RR>md) change(rs,md+,r,LL,RR,vl); upd(tr,l,r);
}
signed main() {
#ifdef JACK
freopen("NOIPAK++.in","r",stdin);
#endif
while(scanf("%d",&n),n!=) { memset(cnt,,sizeof(cnt)),memset(sum,,sizeof(sum)); tot=;
for(R i=;i<=n;++i) { register double l,p,r,b;
scanf("%lf%lf%lf%lf",&l,&p,&r,&b);
d[++tot]=l,L[tot]=ln(l,r,p,);
d[++tot]=r,L[tot]=ln(l,r,b,-);
} sort(d+,d+tot+),sort(L+,L+tot+);
n=unique(d+,d+tot+)-d-; register double ans=;
for(R i=;i<=tot;++i) {
R l=lower_bound(d+,d+n+,L[i].l)-d;
R r=lower_bound(d+,d+n+,L[i].r)-d-;
change(,,n,l,r,L[i].w);
ans+=sum[]*(L[i+].x-L[i].x);
} printf("Test case #%d\nTotal explored area: %.2lf\n\n",++t,ans);
}
}
2019.06.13
最新文章
- 【APP自动化测试】Monkey的测试原理和方法
- Ubuntu 16.04 软件中心闪退 解决方案
- 使用Application Insights 做分析
- spring filter过滤器
- codeforces A. Xenia and Divisors 解题报告
- 让Js顺序执行且回调之
- JS如何获取iframe内html的body值
- AJAX应用中必须要掌握的知识!
- Java的“影子克隆”和“深度克隆”
- 201521123066 《Java程序设计》 第二周学习总结
- 几个SQL命令的使用
- 深度探索C++对象模型
- (办公)TOKEN
- CentOS安装VLC
- git 拉取分支代码 合分支
- Ionic目录结构
- php5.4安装fileinfo扩展
- 为什么 Redis 重启后没有正确恢复之前的内存数据
- stl string 使用指定的分隔符分割成数个子字符串
- Linux FFmpeg(含x264、lame插件)安装记录