I was given a problem to solve using divide and conquer but I don’t know how to do it. It goes like that: You’re given N (where: 3<=N<=3*10^3) pairs {x,y} which represent coordinates of some points. Find amount of pairs of pooints {(x1,y1),(x2,y2)} such that in a rectangle (x1,y1),(x2,y1),(x2,y2),(x1,y2) is no other point.

I know how to solve this problem in N^3 but it’s too slow.