Autor da análise: gabrielrcp
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2383
Resumo
Dados $n$ ($n \leq 10^4$) discos, cada uma com uma cor, desenha-los num grid $X_{size} \times Y_{size}$ ($1 \leq X_{size} , Y_{size} \leq 10^3$)
Solução
Vamos desenha-las linha por linha. Note que se nos restringirmos à uma linha, cada disco vira um intervalo (possivelmente vazio). Assim restringimos nosso problema à pintar intervalos.
Vamos dizer que os discos tenham centros $(x_1, y_1), \ldots, (x_n, y_n)$ e raios $r_1, \ldots, r_n$ e estejamos pintando a linha $y$, $0 \leq y < Y_{size}$. Inicialize um vetor de tamanho $X_{size}$ com alguma flag (-1 por exemplo).
Para uma circunferência k, teremos que o intervalo associado à ela na linha $y$ será vazio se $|y-y_k| > r_k$ e caso contrário terá limites a esquerda e a direita dados por:
(1)Percorra as cicunferências da última para a primeira, para cada circunferência $k$, percorra $x$ de $L_e(k)$ até $L_d(k)$ inclusive. Mas em vez de usar incrementos de 1, faça o seguinte:
- Se a posição atual não estiver pintada, marque que ela agora é do disco $k$, e incremente $x$ em 1.
- Se a posição atual ja estiver pintada por um disco $m$, não a altere, e avance x para $L_d(m) + 1$.
Depois disso, imprima a linha atual com as cores correspondentes à cada disco.
Complexidade
Eu estou com dificuldades para fazer a análise dessa solução. O máximo que eu consigo dizer é que ela realiza $\mathcal O (n X_{size} Y_{size})$, que é bem alto (e não deveria passar no tempo). Mas não consigo montar casos em que esse limite seja atingido. E minha implementação passa bem rápido.
Testes
Entrada
5 5 1
2 2 1 3
Saída
00000
00300
03330
00300
00000
Discuta o problema