bluemmb's blog

Maximum number of points in a rectangle ?
By bluemmb, 8 years ago, In English

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 !!! )

  • Vote: I like it
  • +19
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +5 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ...

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Whats your n^3 solution?

    → Reply