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

Download