Autor da análise: 
natan_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)$$.
Discuta o problema
Natan, alterei um pouco o texto da solução para tentar melhorar a notação. Eu acho que ficou um pouco mais claro, mas ainda não está muito bom. Se preferir pode voltar a versão anterior.
Obrigado Márcio.
O texto para mim parece claro, mas eu acho que estou viciado nele. Você poderia me dizer as partes que não estão muito claras para eu tentar melhorar?
Para mim o problema mesmo foi aquele $V_{ix}$. Eu demorei para entender o que significava.
Como voces trataram o infinito e menos infinito?
Eu tava tratando colocando dois pontos a mais (-4000 e 4000), mas to tomando WA.
Alguma outra idéia de caso chato?
Desculpem, eu já consegui.
Eu alterei, coloquei menos infinito como o mínimo - 100 e mais infinito como maximo + 100.
Ainda tive que tratar especial o caso em que todos as torres tem a mesma coordenada y.
Boa.
Eu não disse mas quando dois pontos tem mesma coordenada y nas minhas contas vai aparecer uma divisão por zero.
Esqueci de comentar isso.
Fora isso não precisa tratar muita coisa.
Depois de várias tentativas de identificar onde estava o problema com o G++ do PKU, observei que os WA's indevidos apareciam quando tinha ponto flutuante na solução, como foi o caso desse problema. Peguei um outro peoblema que tbm dava isso e troquei o printf por cout, enquanto a versão com printf não passou, a versão com cout passou, as duas submissões foram feitas com G++.
Tinha um aviso flutuante em vermelho no PKU que dizia que eles fizeram upgrade para o gcc-4.4.0 e com isso passaram a ser mais rígidos quanto ao padrão ANSI. Em particular, o printf não aceita "%lf" para imprimir double. O correto é "%f". Para ler com scanf o correto é "%lf". Eu li as man pages (man 3 printf) e fiquei chocado com isso, pois até agora eu acreditava que o correto era "%lf" para os dois. Tomei wrong answer por causa disso em outro problema e depois nunca mais cometi o mesmo erro.
Se seu programa (como o meu) estava usando "%lf" para imprimir doubles, na verdade o erro era seu mesmo e não é culpa do gcc. :-)
Acho que o aviso deles está atualmente no FAQ.
É verdade. Eu tinha lido aquilo e pra mim quando eu li só falava desse tal de %lg, será que eles atualizaram o faq ou eu num prestei atenção?
Enfim, há um tempo atrás eu só usava %f no printf porque o gcc reclamava, nunca entendi exatamente como isso funciona =P, recentemente o gcc parou de reclamar e eu passei a usar %lf. Devia ter ficada com o %f… Depois eu mando com %f para ver o que dá.
Que esquisito… isso não devia dar um compile error?
Compile error não, no máximo um warning. Uma função que é varidic como o printf não força os tipos dos parametros extras, pode ser qualquer tipo, a interpretação da string de formato é por conta da função e só pode ser feita em tempo de execução, é claro que o gcc quebra um galho e faz uma verificação em tempo de compilação e emite warnings se encontrar algum problema.
Mas eu tenho quase certeza que aquele aviso flutuante apareceu só depois que eu tive problema com o area 51 =P.
Não consigo pasar o problema, alguien pode colaborar con su formato de impresion?
No meu vetor resp tem os pontos de cruzamento com o eixo x representando os intervalos pedidos no enunciado.
Assuma que SZ(resp) te dê o tamanho do vetor resp.
INF = 100000000.0
e EPS = 1e-9
Obrigado Natan, Já consegui pasar xD, agora já posso dormir tranquilo :D