NUCLEAR - Hai nhà máy điện nguyên tử

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#define ii pair<int, int>
#define iv pair<ii, ii>
#define X first
#define Y second
const int ASK = 1;
const int UPD = 0;
const int N = 300005;
const int M = N + N;
using namespace std;

int n, q, m, maxR;
ii a, b, house[N];
iv Q[N + N];
int bit[M], res[M], Fa[M], Fb[M];

int dist(ii A, ii B)
    {return ceil(sqrt(pow(A.X - B.X, 2) + pow(A.Y - B.Y, 2)));}

void Upd(int i) {for(i++; i <= maxR + 1; i += i & -i) bit[i]++;}
int Get(int i) {int s = 0; for(i++; i; i -= i & -i) s += bit[i]; return s;}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d %d\n", &house[i].X, &house[i].Y);
    scanf("%d %d %d %d %d", &a.X, &a.Y, &b.X, &b.Y, &q);
    for(int i = 1; i <= n; i++) {
        house[i] = ii(dist(house[i], a), dist(house[i], b));
        Fa[house[i].X]++; Fb[house[i].Y]++;
        maxR = max(maxR, max(house[i].X, house[i].Y));
    }
    for(int i = 1; i <= q; i++) {
        scanf("%d %d", &Q[i].X.X, &Q[i].X.Y);
        Q[i].Y.X = ASK; Q[i].Y.Y = i;
        maxR = max(maxR, max(Q[i].X.X, Q[i].X.Y));
    }
    for(int i = 1; i <= maxR; i++) Fa[i] += Fa[i - 1], Fb[i] += Fb[i - 1];
    for(int i = 1; i <= n; i++)
        Q[q + i] = iv(house[i], ii(UPD, 0));
    int m = q + n;
    sort(Q + 1, Q + 1 + m);
    for(int i = 1; i <= m; i++) {
        int x = Q[i].X.X, y = Q[i].X.Y;
        int t = Q[i].Y.X, p = Q[i].Y.Y;
        if (t == UPD) Upd(y);
        else res[p] = Fa[x] + Fb[y] - Get(y);
    }
    for(int i = 1; i <= q; i++) printf("%d\n", res[i]);
	return 0;
}

Download