Base Station

Time Limit: 20000/10000MS (Java/Others)

Memory Limit: 512000/256000KB (Java/Others)

Problem Description

 

移动通信系统中。通信网的建立主要通过基站来完毕。

基站能够分为主基站和子基站。子基站和各个移动用户进行连接，子基站必须通过主基站来和外界实现通信。主基站能够覆盖到的范围是一个圆形区域，子基站和主基站的距离小于半径r才干被该主基站覆盖到。半径r由主基站的发射功率确定。

某个区域的移动通信网，包括2个主基站和N个子基站。它们的位置都能够相应到一个整数坐标上。假设子基站至少被一个主基站覆盖。则该子基站是激活的。

如今通信公司在调试设备，它们不停地改变主基站的发射功率。当两个主基站的覆盖半径分别为r1和r2时，须要知道有多少个子基站处于非激活状态。

 

 

 

Input

有若干组输入数据。

第一行是四个整数：x1、y1、x2、y2（1<=x1、y1、x2、y2<=10^9），表示两个主基站的坐标是（x1,y1）和（x2,y2）。

第二行是一个整数N（1<=N<=100000），表示有N个子基站。

接下来的N行。每行两个整数x、y(1<=x, y<=10^9)。表示每一个子基站的坐标。

接下来一行包括一个整数M（1<=M<=100000），表示有M个询问。

接下来的M行。每行两个整数r1、r2(1<=r1, r2<=10^9)。表示询问当两个主基站的覆盖半径为r1和r2时。处于非激活状态的子基站数。

Output

对每一个查询，输出答案。

Sample Input

1 10 5 252 61 93 86 74 1251 13 28 22 23 2

Sample Output

53043

Hint

Source

kuangbin

Manager

将基站到2个主站的距离^2表示成二维坐标

则本题的询问表示成半径^2

本题等价于“平面上有n个点，问n-横坐标<r1或纵坐标<r2的点数".

用树状数组维护。先依照x从小到大插入，询问y值，得到左下角点数->左上角点数。

接着用容斥。求右上角的点数

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i
              
               =0;i--)#define Forp(x) for(int p=pre[x];p;p=next[p])#define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (100000007)#define MAXN (100000+10)#define MAXXi (1000000000)#define MAXM (100000+10)long long mul(long long a,long long b){return (a*b)%F;}long long add(long long a,long long b){return (a+b)%F;}long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}typedef long long ll;int n,X1,Y1,X2,Y2,m,tot;int lowbit(int x){return x&(-x);}ll sqr(ll x){return x*x;}ll dis2(ll x1,ll y1,ll x2,ll y2){return sqr(x1-x2)+sqr(y1-y2);}struct arr_tree{ int a[MAXN+MAXM*6]; void reset(){ MEM(a) } void add1(int x) { for(;x<=tot;x+=lowbit(x)) a[x]++; } int sum(int x) { int ans=0; for(;x>0;x-=lowbit(x)) ans+=a[x]; return ans; }}T;struct node{ ll x,y; //距离^2 friend bool operator<(node a,node b){return a.x