Блог пользователя bluemmb

Maximum number of points in a rectangle ?
Автор bluemmb, 8 лет назад, По-английски

Hi. I'm stuck with this problem.

Problem : Given set of distinct points and a number A. You have to find maximum number of points in a rectangle with 0 < area <= A.

I have written many different solutions for it but all of them have failed ...

Basic idea is choosing a fixed width and find largest possible height then find maximum number of points in current fixed size rectangle ... I have solved latest problem once by segment tree(Wrong Answer) and once simply by two pointers(Wrong Answer) ...

Can someone help me ? thanks in advance ...

UPDATE

The problem was that LiveArchieve didn't work correctly ...

I got accepted in POJ with modifying and optimizing above solutions : SegmentTree , TwoPointer( I couldn't compute it's complexity but I think it can be huge , however , It got accepted !!! )

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Maybe one of your solutions is really correct.

The problem is: live archive isn't working correctly, all submissions are getting "Wrong Answer" or "Compilation Error".

Yesterday I lost 2 hours trying to debug a correct solution. If you have an Accepted code from another problem, send it again, it will lead to WA.

Try to find this problem on another judge. :P

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    Good day to you

    since LA is down, you can try POJ, which shall be working (yet I have doubts about support new C++)

    Good Luck & Have Nice Day

    EDIT: Seems Live-Archive is alive!

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Thanks both! So that's why I am getting WA instead of TimeLimit!!! I am going to test them in POJ...

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hints for the problem? I can only think of a O(n3) solution.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks. There is better solution, Segment Tree code even without this optimization

    if ( (m/w) == (m/(w+1)) ) continue; is O(n^2logn) in this problem ...

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Whats your n^3 solution?

    → Ответить