Hello, I think I worked out the common problem afflicting many solutions that work on only 32/35 test-cases. I updated my own post from earlier where I also sought help with my initial solution, which worked on only 32 test-cases. But I figured it would be more useful to others if a separate post were made as well.

The problem that afflicted my solution, and I suspect many other people's solutions, is that we are not weighting our rectangles correctly. Specifically, there is a difference between the number of points in a rectangle and the rectangle's area. A rectangle's area is calculated as follows: (x2 - x1) * (y2 - y1). But remember that the problem parameters allow points in the perimeter to be sampled. Let x1 = 1, y1 = 1, x2 = 2, y2= 2, and consider the below illustration:
(1, 2) (2, 2)
(1, 1) (2, 1)

Clearly, there are four points to sample from. But if we use the equation (x2 - x1) * (y2 - y1), we get (2-1)(2-1) = 1; our answer is missing 3/4 points! When the area is calculated, the result is the number of points within the perimeter. This is a 1x1 square, so there is one point within, as the calculation indicates. But since we we want to include the perimeter points, we need to calculate the area of a rectangle that contains the entirety of this one, perimeter included. To do that, we need the area of a rectangle one unit wider and taller, like so:

(0, 3) (1, 3) (2, 3) (3, 3)
(0, 2) (1, 2) (2, 2) (3, 2)
(0, 1) (1, 1) (2, 1) (1, 3)
(0, 0) (1, 0) (2, 0) (3, 0)

Notice that all the points from before are contained within this new, larger rectangle. So the calculation we really need is (x2 - x1 + 1) * (y2 - y1 + 1).

Edit: There was a question (since removed?) asking why this adjustment affects anything. While the weights change, the question is why that change matters, given bigger rectangles are selected more than smaller rectangles no matter which formula is used for the area. It's because the proportions do actually vary between the two cases. Consider again a 1x1 square. Also consider a 3x5 rectangle. The 3x5 rectangle is 15 times larger than the 1x1 square. But now add one-unit to the height and width of both rectangles, meaning we now have a 2x2 square and 4x6 rectangle with areas 4 and 24 respectively. 24/4 = 6, which is clearly not 15. In general, addition to the perimeters of shapes does not keep proportional their areas. Proportions are maintained between shapes if both grow by the same proportion, which can be done by multiplying the dimensions of each shape by some constant scale factor. In this example, with a scale factor of C, using the same starting rectangles, we get a (1C) x (1C) and (3C) x (5C) rectangles. Note that (3C) x (5C) / [(1C) x (1C)] = C^2 * 15 / (C^2 * 1) = 15 / 1 because the scale factor cancels out.