Recentemente, tenho encontrado com frequência problemas de contagem de pontos em um plano bidimensional. Vou fazer um resumo.
CDQ Divide and Conquer
BZOJ1935 – O Jardineiro
Link do problema: BZOJ1935 (link simbólico). Solução disponível em outro post.
BZOJ1176 – Mokia
Link do problema: BZOJ1176 (link simbólico).
Distance (2019 Niuk Duoxiao 8ª, Problema D) – CDQ + BIT
Link do problema: ... Solução: ...
Árvore Segmentária
PUBG 1V3 – CSUST2015
Descrição
A história se baseia no jogo PUBG. Existem \(n\) pessoas, divididas em \(m\) times, cada time com no máximo 4 jogadores. Cada pessoa tem uma área de ataque quadrada definida por \(|x - x_i| \le d_i, |y - y_i| \le d_i\). São dadas as coordenadas \((x_i, y_i)\), o alcance \(d_i\) e o time de cada pessoa. Há \(q\) consultas: para um time informado, qual o número máximo de inimigos dentro da área de ataque de um dos membros desse time?
Ideia
Minha abordagem é um pouco ingênua e mais lenta que a oficial. Uso uma árvore segmentária para manter a contagem de pessoas em cada coordenada \(y\). Para cada pessoa, divido o intervalo em dois eventos: um em \(x_i - d_i - 1\) (subtraio a conatgem na faixa \([y_i - d_i, y_i + d_i]\)) e outro em \(x_i + d_i\) (adição da mesma faixa). Após processar todos os eventos ordenados por \(x\), obtenho o número de pessoas no retângulo \([x_i - d_i, x_i + d_i] \times [y_i - d_i, y_i + d_i]\). Removo os aliados do mesmo time manualmente.
Código
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000000 + 10;
struct Point {
int x, y;
bool operator<(const Point &o) const { return x < o.x; }
} pts[MAXN];
struct Event {
int type, x, id, d, y;
bool operator<(const Event &o) const { return x < o.x; }
} events[MAXN * 3];
struct SegTree {
int l, r, sum;
} seg[MAXN * 12];
int n, m, q, team;
int xs[MAXN], ys[MAXN], ds[MAXN], teamOf[MAXN];
int ans[MAXN], fin[MAXN];
int memberList[MAXN][5]; // para cada time, lista de índices
int memCnt[MAXN];
int coord[MAXN * 3], cntCoord;
int getId(int val) {
return lower_bound(coord + 1, coord + cntCoord + 1, val) - coord;
}
void build(int node, int l, int r) {
seg[node].l = l; seg[node].r = r; seg[node].sum = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
}
void update(int node, int pos) {
if (seg[node].l == seg[node].r) { seg[node].sum++; return; }
int mid = (seg[node].l + seg[node].r) >> 1;
if (pos <= mid) update(node*2, pos);
else update(node*2+1, pos);
seg[node].sum = seg[node*2].sum + seg[node*2+1].sum;
}
int query(int node, int l, int r) {
if (seg[node].l == l && seg[node].r == r) return seg[node].sum;
int mid = (seg[node].l + seg[node].r) >> 1;
if (r <= mid) return query(node*2, l, r);
else if (l > mid) return query(node*2+1, l, r);
else return query(node*2, l, mid) + query(node*2+1, mid+1, r);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d%d", &xs[i], &ys[i], &ds[i], &teamOf[i]);
int t = teamOf[i];
memberList[t][++memCnt[t]] = i;
coord[++cntCoord] = ys[i];
coord[++cntCoord] = ys[i] + ds[i];
coord[++cntCoord] = ys[i] - ds[i];
pts[i] = {xs[i], ys[i]};
}
sort(coord + 1, coord + cntCoord + 1);
cntCoord = unique(coord + 1, coord + cntCoord + 1) - coord - 1;
sort(pts + 1, pts + n + 1);
build(1, 1, cntCoord);
int totEvents = 0;
for (int i = 1; i <= n; ++i) {
int yid = getId(ys[i]);
events[++totEvents] = {1, xs[i] - ds[i] - 1, i, ds[i], yid};
events[++totEvents] = {2, xs[i] + ds[i], i, ds[i], yid};
}
sort(events + 1, events + totEvents + 1);
int ptr = 1;
for (int i = 1; i <= totEvents; ++i) {
while (ptr <= n && pts[ptr].x <= events[i].x) {
update(1, getId(pts[ptr].y));
++ptr;
}
int lower = getId(ys[events[i].id] - events[i].d);
int upper = getId(ys[events[i].id] + events[i].d);
if (events[i].type == 1)
ans[events[i].id] -= query(1, lower, upper);
else
ans[events[i].id] += query(1, lower, upper);
}
for (int i = 1; i <= n; ++i) {
int t = teamOf[i];
for (int j = 1; j <= memCnt[t]; ++j) {
int idx = memberList[t][j];
int xd = xs[idx], yd = ys[idx];
if (xd >= xs[i] - ds[i] && xd <= xs[i] + ds[i] &&
yd >= ys[i] - ds[i] && yd <= ys[i] + ds[i])
--ans[i];
}
fin[teamOf[i]] = max(fin[teamOf[i]], ans[i]);
}
scanf("%d", &q);
while (q--) {
scanf("%d", &team);
printf("%d\n", fin[team]);
}
return 0;
}
Popping Balloons – 2019 Niuk Duoxiao 10ª, Problema F
Descrição
Há \(n\) balões num plano. O jogador pode escolher três linhas horizontais (distância fixa \(r\) entre elas) e três verticais (mesma distância). Qual o número máximo de balões que podem ser estourados?
Idiea
Usamos uma árvore segmentária para manter, para cada \(y\) mais baixo, a quantidade de balões que seriam atingidos. Percorremos as coordenadas \(x\) candidatas (a mais à esquerda) e removemos temporariamente os balões nas três faixas vertciais, consultamos o melhor \(y\) e somamos de volta.
Código
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 100000 + 10;
struct SegTree {
int mx;
} seg[MAXV * 4];
int n, r;
vector<int> ptsByX[MAXV];
void build(int node, int l, int r) {
seg[node].mx = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
}
void modify(int node, int l, int r, int pos, int delta) {
if (l == r) { seg[node].mx += delta; return; }
int mid = (l + r) >> 1;
if (pos <= mid) modify(node*2, l, mid, pos, delta);
else modify(node*2+1, mid+1, r, pos, delta);
seg[node].mx = max(seg[node*2].mx, seg[node*2+1].mx);
}
int main() {
scanf("%d%d", &n, &r);
build(1, 0, MAXV-1);
for (int i = 0; i < n; ++i) {
int x, y; scanf("%d%d", &x, &y);
ptsByX[x].push_back(y);
if (x - r >= 0) ptsByX[x - r].push_back(y);
if (x - 2*r >= 0) ptsByX[x - 2*r].push_back(y);
modify(1, 0, MAXV-1, y, 1);
if (y - r >= 0) modify(1, 0, MAXV-1, y - r, 1);
if (y - 2*r >= 0) modify(1, 0, MAXV-1, y - 2*r, 1);
}
int answer = 0;
for (int x = 0; x < MAXV; ++x) {
for (int y : ptsByX[x]) {
modify(1, 0, MAXV-1, y, -1);
if (y - r >= 0) modify(1, 0, MAXV-1, y - r, -1);
if (y - 2*r >= 0) modify(1, 0, MAXV-1, y - 2*r, -1);
}
answer = max(answer, (int)ptsByX[x].size() + seg[1].mx);
for (int y : ptsByX[x]) {
modify(1, 0, MAXV-1, y, 1);
if (y - r >= 0) modify(1, 0, MAXV-1, y - r, 1);
if (y - 2*r >= 0) modify(1, 0, MAXV-1, y - 2*r, 1);
}
}
printf("%d\n", answer);
return 0;
}
Rikka with Cake – 2019 HDU Duoxiao 02
Descrição
Em um plano \(n \times m\) existem \(k\) raios (semirretas). Quantas regiões o plano é dividido?
Ideia
O número de regiões é igual ao número de interseções + 1. Usamos ordenação por \(x\) e árvore segmentária para contar interseções.
Código
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 400000 + 10;
struct Event {
int type, x, y, yy; // type: 1=add, 2=remove, 3=query vertical
bool operator<(const Event &o) const {
if (x != o.x) return x < o.x;
return type < o.type;
}
} evt[MAXN * 6];
struct SegTree {
ll sum;
int lazy;
} seg[MAXN * 12];
int T, n, m, q, tot;
int xs[MAXN], ys[MAXN];
char dirs[MAXN][3];
int coord[MAXN * 6], cnt;
int getIdx(int v) {
return lower_bound(coord + 1, coord + cnt + 1, v) - coord;
}
void push(int node) {
if (seg[node].lazy) {
seg[node*2].sum += seg[node].lazy;
seg[node*2].lazy += seg[node].lazy;
seg[node*2+1].sum += seg[node].lazy;
seg[node*2+1].lazy += seg[node].lazy;
seg[node].lazy = 0;
}
}
void build(int node, int l, int r) {
seg[node].sum = seg[node].lazy = 0;
if (l == r) return;
int mid = (l+r)>>1;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
}
void add(int node, int l, int r, int pos, ll delta) {
if (l == r) {
seg[node].sum += delta;
seg[node].lazy += delta;
return;
}
push(node);
int mid = (l+r)>>1;
if (pos <= mid) add(node*2, l, mid, pos, delta);
else add(node*2+1, mid+1, r, pos, delta);
seg[node].sum = seg[node*2].sum + seg[node*2+1].sum;
}
ll query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return seg[node].sum;
push(node);
int mid = (l+r)>>1;
ll res = 0;
if (ql <= mid) res += query(node*2, l, mid, ql, qr);
if (qr > mid) res += query(node*2+1, mid+1, r, ql, qr);
return res;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &q);
cnt = 0; tot = 0;
coord[++cnt] = -1; coord[++cnt] = 0; coord[++cnt] = m; coord[++cnt] = m+1;
for (int i = 1; i <= q; ++i) {
scanf("%d%d%s", &xs[i], &ys[i], dirs[i]);
coord[++cnt] = ys[i];
coord[++cnt] = ys[i] + 1;
coord[++cnt] = ys[i] - 1;
}
sort(coord + 1, coord + cnt + 1);
cnt = unique(coord + 1, coord + cnt + 1) - coord - 1;
build(1, 1, cnt);
for (int i = 1; i <= q; ++i) {
char d = dirs[i][0];
if (d == 'L') {
evt[++tot] = {1, 0, ys[i], 0};
evt[++tot] = {2, xs[i] + 1, ys[i], 0};
} else if (d == 'R') {
evt[++tot] = {1, xs[i], ys[i], 0};
evt[++tot] = {2, n + 1, ys[i], 0};
} else if (d == 'U') {
evt[++tot] = {3, xs[i], ys[i], m};
} else { // 'D'
evt[++tot] = {3, xs[i], 0, ys[i]};
}
}
sort(evt + 1, evt + tot + 1);
ll ans = 1;
for (int i = 1; i <= tot; ++i) {
if (evt[i].type == 1) {
add(1, 1, cnt, getIdx(evt[i].y), 1);
} else if (evt[i].type == 2) {
add(1, 1, cnt, getIdx(evt[i].y), -1);
} else {
int l = getIdx(evt[i].y), r = getIdx(evt[i].yy);
ans += query(1, 1, cnt, l, r);
}
}
printf("%lld\n", ans);
}
return 0;
}