PKU 2383 - Circle Drawing

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)

\begin{align} L_e(k) = \max \left\{0, x_k - \lfloor\sqrt{r_k^2 - (y-y_k)^2}\rfloor \right\} \end{align}

(2)

\begin{align} L_d(k) = \min \left\{ X_{size} - 1, x_k + \lfloor\sqrt{r_k^2 - (y-y_k)^2}\rfloor \right\} \end{align}

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

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema