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;
}

Download