PKU 2791 - Area 51

Autor da análise: natan_limanatan_lima

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2791

Resumo

São dados uma sequência de letras e $$m$$ pontos $$(x,y)$$ com coordenadas inteiras e com $$y > 0$$. Uma letra é associada a cada ponto.
O objetivo é imprimir intervalos de pontos no eixo x que não enxergam 2 pontos ao mesmo tempo e onde os pontos da entrada formam a sequência dada quando vistos no sentido horário a partir dos pontos dentro destes intervalos.

Detalhes:
Alguns pontos podem ter o mesmo nome.
Não existem 2 pontos com mesmas coordenadas $$x$$ e $$y$$.

Solução

Primeiro devemos notar que os únicos lugares onde a sequência muda são os pontos no eixo x que derivam do cruzamento entre uma reta formada por 2 pontos quaisquer do conjunto da entrada e o eixo x. Com isso podemos resolver o problema da seguinte forma:
Seja V o conjunto de todos os pontos citados acima unidos com os ponto $$(-\infty,0)$$ e $$(\infty,0)$$.
Ordene V pela coordenada x e sejam $P^1, P^2, \ldots, P^m$ os pontos de V nessa ordem.

Para todo $i = 1, 2, \ldots, m-1$, considere a ordenação no sentido horário dos pontos da entrada que tem como pivo o ponto $((P^i_{x} + P^{i+1}_{x})/2 , 0)$ então se esta ordenação bate com a sequência, temos que os pontos que tem x no intervalo $$]P^i_x , P^{i+1}_x[$$ também enxergam a sequência da maneira pedida, pelo fato de que a sequência muda apenas quando cruzamos esses pontos de intersecção.

Para ordenarmos os pontos dessa maneira basta usarmos o sort do c++ e a função de comparação necessária é a operação primitiva esquerda.

Esta primitiva consiste em sabermos a posição de um ponto em relação a um vetor (segmento orientado). Então dados três pontos A, B e C tal que AB é um segmento orientado, temos que a primitiva Esquerda(A,B,C) é verdadeira se o ponto C está a esquerda da reta formada ao estendermos o segmento AB nos dois sentidos. A primitiva é falsa caso contrário.

Pode ser implementada da seguinte maneira:

bool esquerda(ponto a,ponto b,ponto c){
   return ((b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y)) < 0;
}

Para calcular os pontos de intersecção entre a reta que passa por dois pontos A e B e o eixo x, basta seguirmos a seguinte linha de raciocínio:
Uma reta pode ser definida por dois pontos da seguinte forma: $$(A_x,A_y) + \alpha(A_x - B_x, A_y - B_y) $$
Queremos encontrar um $$\alpha$$ onde $$A_y + \alpha(A_y-B_y) = 0$$. Logo o $$\alpha$$ pedido é $$-A_y / (A_y - B_y)$$
e a coordenada x do ponto que queremos é $$A_x - \alpha*(A_x - B_x)$$.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License