"
题目链接
求平面n个点（n<=15000）,用一个 长宽为 s w的矩阵去套，能套到的最多的点数，在边上的点也算
其实跟之前矩形//代码效果参考：https://v.youku.com/v_show/id_XNjQwMDE0MjY5Ng==.html
嵌套求面积类似 （POJ的atlantic）用类似扫描线的做法，把点当做边 （y 到 y值+w），插入线段树，这样就维护了y方向，x方向就用类似队列维护，在距离大于s的时候，就弹出前面的（即线段树移除那条边），一边添加当前边
维护一个值，看从前扫到后，边层数累积的最多的时候即可。
一开始还以为要维护覆盖值，后来发现没用，直接一个d维护积累层数即可。
一开始输入那里没写好EOF，RE了几次，不知道什么原因，改完之后1A
?123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107#include #include #include #include #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
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
"
