题目大意
平面上有两个圆,坐标分别为 (xa,ya) 、 (xb,yb) ,还有 n 个点,坐标分别为(xi,yi)。
有 q 个询问,每次给出两个圆各自半径r1和 r2 。要求输出有多少个点被至少一个圆覆盖(圆周也算在内)。
本题所有数字都为整数。
1≤n≤200000,1≤q≤100000,−100000≤x,y≤100000,0≤r≤300000
题目分析
一个点 (x,y) 在半径为 r 、圆心为(x0,y0)的圆内(或圆上)当且仅当:
(x0−x)2+(y0−y)2≤r2
在题目中圆心和点的位置都是在询问前知道的,于是我们提前计算每个点与两个圆心不等式左边式子的值,也就是到圆心距离的平方,用这两个值作为新的关键字。
那么给出 r 之后,小于等于r2的关键字个数就是被这个圆覆盖的点的个数。
如果是一个圆,那我们直接快排二分就行了,但是这里是两个圆,答案为两个圆各自覆盖的点的个数和减去同时覆盖的点的个数。
怎么求同时满足两个小于等于的约束的点的个数呢?我们将两个新的关键字( xn 和 yn )作为每个点的坐标,那么这个约束就可以看成平面中一个小平面 [0...xn][0...yn] 内点的个数。
显然我们可以对其中一维排序,另一位离散化之后在数据结构中插值。显然这里选用主席树是最好的。
时间复杂度 O((n+q)logn2) ,空间复杂度 O(nlogn2) 。
当然,这是这题对询问在线的做法,如果通过对询问离线的方法,我们可以用更加简单的树状数组等数据结构来做,空间复杂度可以降为 O(n) 。个人认为主席树代码复杂度并不大,换离线方法也不会好到哪里去,于是在这里不讨论离线做法。
代码实现
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
using namespace std;
typedef long long LL;
int read()
{
int x=,f=;
char ch=getchar();
while (!isdigit(ch))
{
if (ch=='-')
f=-;
ch=getchar();
}
while (isdigit(ch))
{
x=x*+ch-'0';
ch=getchar();
}
return x*f;
}
const int N=;
const int S=;
struct P
{
int xn,yn;
LL x,y;
P (LL x0=,LL y0=){x=x0,y=y0;}
}p[N+],A,B;
P operator-(P a,P b)
{
return P(a.x-b.x,a.y-b.y);
}
struct D
{
LL v;
int id,rank;
}s[][N+];
bool operator<(D a,D b)
{
return a.v<b.v;
}
int n,m,cnt1,cnt2;
struct Chairman_Tree
{
int son[S+][],size[S+];
int root[N+];
int tot;
void init()
{
memset(son,,sizeof son);
memset(size,,sizeof size);
memset(root,,sizeof root);
tot=;
root[]=newnode();
}
int newnode()
{
son[tot][]=son[tot][]=size[tot]=;
return tot++;
}
void insert(int &rt,int rt0,int l,int r,int x)
{
rt=newnode();
son[rt][]=son[rt0][];
son[rt][]=son[rt0][];
size[rt]=size[rt0]+;
if (l==r)
return;
int mid=l+r>>;
if (x<=mid)
insert(son[rt][],son[rt0][],l,mid,x);
else
insert(son[rt][],son[rt0][],mid+,r,x);
}
int query(int rt,int st,int en,int l,int r)
{
if (!rt)
return ;
if (st==l&&en==r)
return size[rt];
int mid=l+r>>;
if (en<=mid)
return query(son[rt][],st,en,l,mid);
else
if (mid+<=st)
return query(son[rt][],st,en,mid+,r);
else
return query(son[rt][],st,mid,l,mid)+query(son[rt][],mid+,en,mid+,r);
}
}t;
int main()
{
freopen("supply.in","r",stdin);
freopen("supply.out","w",stdout);
n=read(),m=read();
A.x=read(),A.y=read(),B.x=read(),B.y=read();
for (int i=;i<=n;i++)
p[i].x=read(),p[i].y=read();
for (int i=;i<=n;i++)
{
P pa=p[i]-A,pb=p[i]-B;
s[][i].v=pa.x*pa.x+pa.y*pa.y,s[][i].v=pb.x*pb.x+pb.y*pb.y;
s[][i].id=i,s[][i].id=i;
}
sort(s[]+,s[]++n);
sort(s[]+,s[]++n);
s[][].v=-;
cnt1=;
for (int i=;i<=n;i++)
{
p[s[][i].id].xn=(s[][i].v!=s[][i-].v)?++cnt1:cnt1;
s[][i].rank=cnt1;
}
s[][].v=-;
cnt2=;
for (int i=;i<=n;i++)
{
p[s[][i].id].yn=(s[][i].v!=s[][i-].v)?++cnt2:cnt2;
s[][i].rank=cnt2;
}
t.init();
for (int i=;i<=n;i++)
t.insert(t.root[i],t.root[i-],,cnt2,p[s[][i].id].yn);
for (int i=,r1,r2;i<=m;i++)
{
r1=read(),r2=read();
LL s1=(LL)r1*r1,s2=(LL)r2*r2;
int l=,r=n,p1=;
while (l<=r)
{
int mid=l+r>>;
if (s[][mid].v<=s1)
{
p1=mid;
l=mid+;
}
else
r=mid-;
}
int p2=;
l=,r=n;
while (l<=r)
{
int mid=l+r>>;
if (s[][mid].v<=s2)
{
p2=mid;
l=mid+;
}
else
r=mid-;
}
p2=s[][p2].rank;
int ans1=p2?t.query(t.root[n],,p2,,cnt2):;
int ans2=t.query(t.root[p1],,cnt2,,cnt2);
int ans3=p2?t.query(t.root[p1],,p2,,cnt2):;
ans1=ans1+ans2-ans3;
printf("%d\n",ans1);
}
fclose(stdin);
fclose(stdout);
return ;
}