C++ Subsets of Points that Can Be Boxed

I have a set of N points in the real plane, and want to know how many subsets of them can "boxed". That is, how many subsets are there such that a rectangle in the real plane with sides parallel to the x and y axis exists with the subset of points all inside and any other points outside. I would much prefer a C++11 solution for this. This is part of a project I'm working on, but its fairly important that it works quickly to minimize loading.

I think convex hulls might be relevant here, but am having a lot of trouble seeing how they would actually help.

Some clarifications:

Since we are on the real plane, you can assume that no points have the exact same x or y coordinate. If it makes the problem easier, you can take the x and y to both be integers with no x or y coordinates being shared.

The empty set and the entire set are counted, though both trivially always work.

The number of points is not unreasonable, about 1000, but that means that straight bashes of all subsets probably won't work. The number of subsets should be able to fit within a long long in C++.