TOPIC

PROBLEM 1938 - URI Fórum 1.0

URI Online Judge asked 6 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Diego Rodrigues replied 5 years ago

    Any tips on what to use to solve this one?

    I could not find a solution even sorting by x values.

  • Rafael Gauna Trindade replied 5 years ago

    Dica pra quem tá com problemas nesse:

    Realmente uma solução n³ é inviável, porém não tanto, em alguns casos de teste o tempo é entre 4~5 segundos. Apesar disso, não serve pro nosso timelimit estipulado.

    Uma dica é ordenar os postes em x ou y e pensar que os pares de postes que formam retângulos sem postes no interior são, para um poste a, o conjunto s de postes que estão no raio máximo de distancia. Todo e qualquer poste fora desse raio vai formar um retângulo com outro poste no meio.

    A complexidade fica quadrática, o que pra 2 <= n <= 3000 é muito viável. Fiz em C e consegui 0.028s

  • Lucas Berg replied 5 years ago

    Verdade Wyllian, consegui passar uma solução O(N²) em 0.032s !

    Porém como aviso para os outros que possam aparecer por aqui, uma solução O(N³) vai tomar Time Limit nos últimos casos de testes de problema.

    MOD
  • Wyllian Brito replied 5 years ago

    @bergolho Uma solução O(N^2) passa com bastante folga :)

  • Lucas Berg replied 5 years ago

    Este problema pode ser resolvido por meio de uma Quad-Tree ? Porque pelos limites do problema qualquer solução O(N^2) não deve passar no tempo limite.

    MOD