首页 > 代码库 > POI 2001 Goldmine 线段树 扫描线
POI 2001 Goldmine 线段树 扫描线
题目链接
http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=1350
http://main.edu.pl/en/archive/oi/8/kop
求平面n个点（n<=15000）,用一个 长宽为 s w的矩阵去套，能套到的最多的点数，在边上的点也算
其实跟之前矩形嵌套求面积类似 （POJ的atlantic）用类似扫描线的做法，把点当做边 （y 到 y值+w），插入线段树，这样就维护了y方向，x方向就用类似队列维护，
在距离大于s的时候，就弹出前面的（即线段树移除那条边），一边添加当前边
维护一个值，看从前扫到后，边层数累积的最多的时候即可。
一开始还以为要维护覆盖值，后来发现没用，直接一个d维护积累层数即可。
一开始输入那里没写好EOF，RE了几次，不知道什么原因，改完之后1A
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,rusing namespace std;const int N = 100020;//int cover[N<<2];int flag[N<<2];int d[N<<2];int s,w,n,maxn;struct node{ int x,y; bool operator < (const node& rhs ) const{ if (x==rhs.x) return y<rhs.y; return x<rhs.x; }}point[15010];bool input(){ maxn=0; if (scanf("%d%d",&s,&w)==EOF) return false; scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d%d",&point[i].x,&point[i].y); point[i].x+=30000; point[i].y+=30000; maxn=max(maxn,point[i].y); } maxn+=w+10; return true;}void build(int rt,int l,int r){ //cover[rt]=0; flag[rt]=0; d[rt]=0; if (l>=r) return; int mid=(l+r)>>1; build(lson); build(rson);}void pushdown(int rt,int l,int r){ if (flag[rt]==0) return; int mid=(l+r)>>1; //cover[rt<<1]+=flag[rt]*(mid-l+1); //cover[rt<<1|1]+=flag[rt]*(r-mid); d[rt<<1]+=flag[rt]; d[rt<<1|1]+=flag[rt]; flag[rt<<1]+=flag[rt]; flag[rt<<1|1]+=flag[rt]; flag[rt]=0;}void up(int rt){ //cover[rt]=cover[rt<<1]+cover[rt<<1|1]; d[rt]=max(d[rt<<1],d[rt<<1|1]);}void remove(int L,int R,int rt,int l,int r){ if (L<=l && r<=R){ //cover[rt]-=(r-l+1); d[rt]--; flag[rt]+=-1; return; } pushdown(rt,l,r); int mid=(l+r)>>1; if (L<=mid) remove(L,R,lson); if (R>mid) remove(L,R,rson); up(rt);}void inserts(int L,int R,int rt,int l,int r){ if (L<=l && r<=R){ //cover[rt]+=(r-l+1); d[rt]++; flag[rt]+=1; return ; } pushdown(rt,l,r); int mid=(l+r)>>1; if (L<=mid) inserts(L,R,lson); if (R>mid) inserts(L,R,rson); up(rt);}int main(){ while (input()){ sort(point+1,point+1+n); build(1,0,maxn); int pre=1; int ans=0; for (int i=1;i<=n;i++){ //cout<<i<<endl; while (point[pre].x+s<point[i].x){ remove(point[pre].y,point[pre].y+w,1,0,maxn); pre++; } inserts(point[i].y,point[i].y+w,1,0,maxn); ans=max(ans,d[1]); } printf("%d\n",ans); }}
POI 2001 Goldmine 线段树 扫描线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。