本文主要是介绍POJ 2482 Stars in Your Window（扫描线），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你10000以内的星星的坐标和星星的亮度（即分别为x,y,c），要求用W*H的矩形去围住一个区域，使得这个区域内的星星的亮度最大，并且要求矩形边框上的星星不计入内。矩形可以平移，但不能旋转。
对于每一个星星，分别建立线(x,y,y+H,c)和(x+W,y,y+H,-c)。这样处理的原因是我们就可以把问题转化成求线段树里某一段内的最大值，即区间查询。矩形边框上的星星不计的处理方法是：1.对于x轴方面的处理是在排序的时候，优先-c的边，因为如果优先+c的边，那么就是将边框上的星星计入了。2.对于y轴方面的，我的处理方法是将线段树的叶子结点处理成长度为1的区间即[0，1]，[1，2]。。。这样，那么在处理比如覆盖范围是在（0，1），（1，2）的边时，就能避免边框的问题，即点2不会被两个边更新到，因为更新的是长度为1的区间。要用离散化。
/*代码风格更新后*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))
const int N=20005;
typedef long long LL;struct Line
{LL x,y1,y2,valu;Line(){}Line(LL a,LL b,LL c,LL d){ x=a;y1=b;y2=c;valu=d; }bool operator<(const Line&b)const{return x<b.x||(x==b.x&&valu<b.valu);}
};
struct node
{int lft,rht;int flag,mx;int mid(){return MID(lft,rht);}void fun(int valu){mx+=valu;flag+=valu;}
};vector<LL> y;
vector<Line> line;
map<LL,int> H;struct Segtree
{node tree[N*4];void build(int lft,int rht,int ind){tree[ind].lft=lft; tree[ind].rht=rht;tree[ind].mx=0; tree[ind].flag=0;if(lft+1!=rht){int mid=tree[ind].mid();build(lft,mid,LL(ind));build(mid,rht,RR(ind));}}void updata(int st,int ed,int ind,int valu){int lft=tree[ind].lft,rht=tree[ind].rht;if(st<=lft&&rht<=ed) tree[ind].fun(valu);else {if(tree[ind].flag){tree[LL(ind)].fun(tree[ind].flag);tree[RR(ind)].fun(tree[ind].flag);tree[ind].flag=0;}int mid=tree[ind].mid();if(st<mid) updata(st,ed,LL(ind),valu);if(ed>mid) updata(st,ed,RR(ind),valu);tree[ind].mx=max(tree[LL(ind)].mx,tree[RR(ind)].mx);}}
}seg;
int main()
{int n,w,h;while(scanf("%d%d%d",&n,&w,&h)!=EOF){y.clear(); H.clear(); line.clear();for(int i=0;i<n;i++){LL a,b,c;scanf("%lld%lld%lld",&a,&b,&c);line.push_back(Line(a,b,b+h,c));line.push_back(Line(a+w,b,b+h,-c));y.push_back(b); y.push_back(b+h); }sort(line.begin(),line.end());sort(y.begin(),y.end());y.erase(unique(y.begin(),y.end()),y.end());for(int i=0;i<(int)y.size();i++) H[y[i]]=i;int mx=0;seg.build(0,(int)y.size()-1,1);for(int i=0;i<(int)line.size();i++){seg.updata(H[line[i].y1],H[line[i].y2],1,line[i].valu);mx=max(mx,seg.tree[1].mx);}printf("%d\n",mx);}return 0;
}
#include <iostream>
/*代码风格更新前*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=20005;
LL order[N];
struct Line
{LL x,y1,y2;int valu;Line(){}Line(LL a,LL b,LL c,int d){x=a;y1=b;y2=c;valu=d;}bool operator < (const Line &b) const {return x<b.x||(x==b.x&&valu<b.valu);}
}line[N];
struct node
{int left,right;int iadd,imax;int mid(){return left+(right-left)/2;}void change(int valu){iadd+=valu;imax+=valu;}
};
struct Segtree
{node tree[N*4];void clear(){memset(tree,0,sizeof(tree));}void build(int left,int right,int ind){tree[ind].left=left; tree[ind].right=right;tree[ind].iadd=0; tree[ind].imax=0;if(left+1!=right){int mid=tree[ind].mid();build(left,mid,ind*2);build(mid,right,ind*2+1);}}void updata(int be,int end,int ind,int valu){int left=tree[ind].left,right=tree[ind].right;if(be<=left&&right<=end) tree[ind].change(valu);else {if(tree[ind].iadd)//懒操作，相当于push_down{tree[ind*2].change(tree[ind].iadd);tree[ind*2+1].change(tree[ind].iadd);tree[ind].iadd=0;}int mid=tree[ind].mid();if(be<mid) updata(be,end,ind*2,valu);if(end>mid) updata(be,end,ind*2+1,valu);tree[ind].imax=max(tree[ind*2].imax,tree[ind*2+1].imax);}}
}seg;
int main()
{int n,w,h;while(scanf("%d%d%d",&n,&w,&h)!=EOF){int res=0;seg.clear();for(int i=0;i<n;i++){int x,y,valu;scanf("%d%d%d",&x,&y,&valu);order[i*2]=y; order[i*2+1]=(LL)y+h;line[i*2]=Line(x,y,(LL)y+h,valu);line[i*2+1]=Line((LL)x+w,y,(LL)y+h,-valu);}sort(line,line+n*2);sort(order,order+n*2);int cnt=unique(order,order+n*2)-order;seg.build(0,cnt,1);for(int i=0;i<n*2;i++){int y1=lower_bound(order,order+cnt,line[i].y1)-order;int y2=lower_bound(order,order+cnt,line[i].y2)-order;seg.updata(y1,y2,1,line[i].valu);res=max(res,seg.tree[1].imax);}printf("%d\n",res);}return 0;
}
这篇关于POJ 2482 Stars in Your Window（扫描线）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
