NUCLEAR - Hai nhà máy điện nguyên tử
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 200200
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define SQR(x) (1LL*(x)*(x))
#define fi first
#define se second
using namespace std;
typedef long long ll;
class FenwickTree {
private:
int n;
vector<int> v;
public:
FenwickTree() {
n=0;
}
FenwickTree(int n) {
this->n=n;
v.assign(n+7,0);
}
void update(int x,int d) {
if (x<1) return;
for (;x<=n;x+=x&-x) v[x]+=d;
}
int get(int x) const {
int res=0;
if (x>n) return (0);
for (;x>=1;x&=x-1) res+=v[x];
return (res);
}
};
struct Query {
ll r1,r2,id;
Query() {
r1=r2=id=0;
}
void input(int id) {
this->id=id;
int _r1,_r2;
scanf("%d%d",&_r1,&_r2);
r1=-SQR(_r1);r2=-SQR(_r2);
}
bool operator < (const Query &x) const {
return (r1==x.r1?r2<x.r2:r1<x.r1);
}
};
pair<int,int> a[MAX];
pair<ll,ll> dis[MAX];
pair<int,int> cen1,cen2;
vector<ll> allDis;
Query query[MAX];
int n,q;
int answer[MAX];
void init(void) {
scanf("%d",&n);
FOR(i,1,n) scanf("%d%d",&a[i].fi,&a[i].se);
scanf("%d%d%d%d%d",&cen1.fi,&cen1.se,&cen2.fi,&cen2.se,&q);
FOR(i,1,q) query[i].input(i);
}
ll distan(const pair<int,int> &a,const pair<int,int> &b) {
return (SQR(a.fi-b.fi)+SQR(a.se-b.se));
}
void precount(void) {
FOR(i,1,n) dis[i]=make_pair(-distan(a[i],cen1),-distan(a[i],cen2));
sort(dis+1,dis+n+1);
FOR(i,1,n) allDis.push_back(dis[i].se);
sort(allDis.begin(),allDis.end());
allDis.resize(unique(allDis.begin(),allDis.end())-allDis.begin());
FOR(i,1,n) dis[i].se=lower_bound(allDis.begin(),allDis.end(),dis[i].se)-allDis.begin()+1;
sort(query+1,query+q+1);
}
void process(void) {
FenwickTree tree(n);
int j=1;
FOR(i,1,q) {
while (j<=n && dis[j].fi<query[i].r1) {
tree.update(dis[j].se,1);
j++;
}
int t=lower_bound(allDis.begin(),allDis.end(),query[i].r2)-allDis.begin();
if (t>n) t=n;
answer[query[i].id]=n-tree.get(t);
}
FOR(i,1,q) printf("%d\n",answer[i]);
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("tmp.txt","r",stdin);
#endif // ONLINE_JUDGE
init();
precount();
process();
return 0;
}