TC SRM 521

p500

n<=40 points on xy-plane, find number of subsets that fit in nxn square, where nlow <= n <= nhigh.

Both nlow and nhigh can be 10^8, as well as x[i] and y[i]. But notice that any subset of points has xmin, xmax, ymin, ymax, and that's only n^4 choices of them. For each choice we have a rectangle and we need to test if it can be fit into a square of size between nlow and nhigh. If it does, we then test each point and collect all points inside this square. We can record all subsets using long long bitmask since n<64. To fit a rectangle into a square, we need to limit rectangle never go off the limit of prev of min and next of max, and putting xval and yval into a set<int> helps.

However, I keep forgetting that the rectangle needs to fit into a square and then the sides of a square is equal. So if x2-x1 and y2-y1 are different, the side is at least max of the two.