NUCLEAR - Hai nhà máy điện nguyên tử
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define sqr(x) (1LL*(x)*(x))
using namespace std;
struct point
{
int z;
long long x, y;
point() {}
point(long long _x, long long _y, int _z)
{
x = _x; y = _y; z = _z;
}
bool operator < (point u) const
{
if (x != u.x) return x < u.x;
if (y != u.y) return y < u.y;
return z < u.z;
}
} a[400400];
int n, q, x[200200], y[200200], ans[200200], tree[400400];
long long d1[200200], d2[200200];
vector <long long> Y;
int calc(long long d[], long long r)
{
return upper_bound(d, d + n, r) - d;
}
int main()
{
int x1, y1, x2, y2;
long long r1, r2;
cin >> n;
for (int i = 0; i < n; i++) scanf("%d%d", x + i, y + i);
cin >> x1 >> y1 >> x2 >> y2 >> q;
for (int i = 0; i < n; i++)
{
d1[i] = sqr(x[i] - x1) + sqr(y[i] - y1);
d2[i] = sqr(x[i] - x2) + sqr(y[i] - y2);
a[i] = point(d1[i], d2[i], -1);
Y.push_back(d2[i]);
}
sort(d1, d1 + n);
sort(d2, d2 + n);
for (int i = 0; i < q; i++)
{
scanf("%lld%lld", &r1, &r2);
r1 *= r1; r2 *= r2;
a[n + i] = point(r1, r2, i);
Y.push_back(r2);
ans[i] += calc(d1, r1) + calc(d2, r2);
}
sort(Y.begin(), Y.end());
Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
sort(a, a + n + q);
for (int i = 0; i < n + q; i++)
{
int y = lower_bound(Y.begin(), Y.end(), a[i].y) - Y.begin();
y++;
if (a[i].z >= 0)
while (y) ans[a[i].z] -= tree[y], y -= y & -y;
else
while (y <= int(Y.size())) tree[y]++, y += y & -y;
}
for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
}