题目:https://www.cometoj.com/contest/59/problem/D?problem_id=2713

题意:给你一个正方形,然后给你n个点,这个正方形能随意放哪,要求那个正方形能覆盖的最多点是多少个

思路:我们其实可以把题目转换一下,我们可以以每个点为中心,我们就可以以那个点+正方形边长,就代表正方形在这个范围内就能覆盖到当前点

然后我们就相当与求一个点被覆盖的最多次数是多少,我们利用扫描线,我们每次入边加进去,然后我们求区间最大值来持续更新即可,因为如果一点

值为3就代表被三个正方形所覆盖,那么选择这个位置就能盖三个点

#include<bits/stdc++.h>
#define maxn 400005
#define mod 1000000007
#define ld (d<<1)
#define rd (d<<1|1)
using namespace std;
typedef long long ll;
struct sss
{
ll l,r,h;
ll val;
sss(){};
sss(ll a,ll b,ll c,ll d){
l=a;
r=b;
h=c;
val=d;
};
}ss[maxn*];
ll X[maxn*];
ll n,k;
ll num;
int cmp(struct sss x,struct sss y){
if(x.h==y.h) return x.val>y.val;
return x.h<y.h;
}
ll sum[maxn*],cnt[*maxn];
ll xx[maxn];
void push_up(int id)
{
sum[id]=max(sum[id*],sum[id*+])+cnt[id];
return ;
}
void modify(int ql,int qr,int flag,int l,int r,int id)
{
//cout<<ql<<" "<<qr<<" "<<l<<" "<<r<<endl;
if(ql<=l&&r<=qr)
{
sum[id]+=flag;
cnt[id]+=flag;
//push_up(id);
return ;
}
int mid=(l+r)/;
if(ql<=mid)
{
modify(ql,qr,flag,l,mid,*id);
}
if(qr>mid)
{
modify(ql,qr,flag,mid+,r,*id+);
}
push_up(id);
return ;
}
int main(){
scanf("%lld%lld",&n,&k);
ll x,y;
for(int i=;i<n;i++){
scanf("%lld%lld",&x,&y);
X[num]=x;
ss[num++]=sss(x,x+k,y,(ll));
X[num]=x+k;
ss[num++]=sss(x,x+k,y+k,(ll)(-));
}
sort(ss,ss+num,cmp);
sort(X,X+num);
int m=unique(X,X+num)-X;
ll mx=;
for(int i=;i<num;i++){
int l=lower_bound(X,X+m,ss[i].l)-X;
int r=lower_bound(X,X+m,ss[i].r)-X;
if(l<=r)
modify(l,r,ss[i].val,,m-,);
mx = max(mx,sum[]);
}
printf("%lld",mx);
}

最新文章

  1. 【poj3270】 Cow Sorting
  2. postman使用之五:Runner的使用
  3. mariadb
  4. 安卓自定义View(一)自定义控件属性
  5. tips javascript(一)
  6. CentOS 7 修改时区(转)
  7. 安装最新版本的ReSharper导致原生全局搜索工具的消失问题
  8. left join与on,where 结合一起用的异同
  9. iso8583报文自学笔记
  10. 1027: [JSOI2007]合金 - BZOJ
  11. C#入门经典(第五版)学习笔记(三)
  12. github jekyll site不再使用Maruku由于Markdown翻译员,但kramdown
  13. 职业定位(Web前端、后台、PC端)
  14. Spark SQL 1.3测试
  15. poj1106
  16. [洛谷P1638]逛画展
  17. Linux 线程编程1.0
  18. .Net Core 2.0 生态(2).NET Core 2.0 特性介绍和使用指南
  19. 静态分析Android程序
  20. v$instance如何生成

热门文章

  1. IPC机制总结
  2. Bugku | Easy_Re
  3. 20175203 2018-2019 实验三 《敏捷开发与XP实践》
  4. Django中执行原生SQL语句【新编辑】
  5. MVC路由解析---IgnoreRoute
  6. Markdown ![...](...) --&gt; &lt;img ... /&gt;
  7. 基于Diff机制的多个状态合并
  8. 实验报告(七)&amp;第九周课程总结
  9. 转 什么是Mbps、Kbps、bps、kb、mb及其换算和区别
  10. Fix invisible cursor issue in Ubuntu 13.10