For this problem. Why can we consider bounding rectangles instead of squares when counting the answers? Will we not count points where only a rectangle can enclose all the points but not a square?
Problem Link: USACO
Editorial Link: Contest Results
the bounding square of a set of points is not unique. the solution describes how to count only bounding rectangles that can be surrounded by a bounding square that doesn’t include any additional points.
I see. I get the idea now. Sorry for the inconvenience but I’m still not entirely sure how the code works.
What is the following code’s function? And how can we make sure there are no additional points that will be included in the square but not the rectangle?
int yl = min(cows[a].s,cows[b].s), yr = max(cows[a].s,cows[b].s);
if (l <= r) yl = min(yl,y[l]), yr = max(yr,y[r]);
assert(yr-yl <= len);