O tempo conta, quer dizer que quem submeter primeiro ganha ou o algoritmo mais rapido?
=P
=P
O algoritmo mais rápido. Ou seja, vou olhar o tempo de CPU que cada um obteve com a sua submissão.
Cris
Cris
Cris, acabei de passar o gift wrapping empatando com os melhores tempos =P
Minha submissão do Graham scan deu exatamente o mesmo tempo do Gift wrapping. E agora?
De teimoso, tou tentando passar o QuickHull, mas tou levando WA.
Estou seguindo mais ou menos o algoritmo dos slides, mas vi que tem um problema na hora de particionar o vetor. De cara a invariante não é satisfeita, já que inicialmente p' = q. Isso dá problema na hora de mover um ponto vermelho quando não tem pontos verdes fora do triângulo. Eu consertei (de uma forma não muito elegante) e para a entrada-exemplo dá certo.
Alguém mais viu esse problema? Não lembro se na aula a gente fez alguma correção...
Murilo
Estou seguindo mais ou menos o algoritmo dos slides, mas vi que tem um problema na hora de particionar o vetor. De cara a invariante não é satisfeita, já que inicialmente p' = q. Isso dá problema na hora de mover um ponto vermelho quando não tem pontos verdes fora do triângulo. Eu consertei (de uma forma não muito elegante) e para a entrada-exemplo dá certo.
Alguém mais viu esse problema? Não lembro se na aula a gente fez alguma correção...
Murilo
Oi Murilo,
Não entendi seu comentário sobre o invariante não valer logo de cara. Olhei nas transparências e acho que eles valem. Não há nenhum ponto na parte verde no início (de p' até q-1, que é um intervalo vazio).
Cris
Não entendi seu comentário sobre o invariante não valer logo de cara. Olhei nas transparências e acho que eles valem. Não há nenhum ponto na parte verde no início (de p' até q-1, que é um intervalo vazio).
Cris
Hum...
Mas se você mover um ponto vermelho e não tiver nenhum verde dá problema, a troca é feita duas vezes.
Murilo
Mas se você mover um ponto vermelho e não tiver nenhum verde dá problema, a troca é feita duas vezes.
Murilo
Oi Murilo,
Tem razão. Não funcionava direito quando a parte verde tava vazia. Tentei consertar. Veja na nova versão das transparências da aula 19 se minhas alterações fazem sentido.
Depois me conte se conseguiu passar a submissão com esse algoritmo.
Obrigada,
Cris
Tem razão. Não funcionava direito quando a parte verde tava vazia. Tentei consertar. Veja na nova versão das transparências da aula 19 se minhas alterações fazem sentido.
Depois me conte se conseguiu passar a submissão com esse algoritmo.
Obrigada,
Cris
Fiz as modificações mas continua não passando. Submeti o código novo na entrada do PACA caso você queira dar uma olhada.