Generalization of Codechef "Rectangles Counting" problem

I have been trying a generalization of the Codechef problem Rectangle Counting. Note that the problem asks only for axis-aligned rectangles. But what if the constraint was removed, i.e. - as in Counting Squares where non-axis aligned squares are considered too. How would we count the rectangles then. The best I can think of is an O(N^3) solution wherein we fix A,B,C of the rectangle and just look for D