This is an incomplete solution. You missed one form of rectangles that make up the answers. You assumed that solution rectangle will always have point(s) lying on its roof, this is not always the case. Answer rectangle could also lie between 2 points with roof aligned to y = 500.
I realized this when I implemented what you said and got WA. Although this is easy to fix. Just include all points of form [i, 500] in your input, i ranging from 0 to 1, 00, 000. (why?)