CF 293D - Ksusha and Square
We are given a convex polygon whose vertices have integer coordinates. Consider every lattice point, meaning every point with integer coordinates, that lies inside the polygon or on its boundary.
Rating: 2700
Tags: geometry, math, probabilities, two pointers
Solve time: 43s
Verified: no
Solution
Problem Understanding
We are given a convex polygon whose vertices have integer coordinates. Consider every lattice point, meaning every point with integer coordinates, that lies inside the polygon or on its boundary.
Among all unordered pairs of distinct lattice points, we choose one pair uniformly at random. Those two points become opposite corners of a square. The task is to compute the expected area of that square.
The geometry of the square is actually the easy part. If two points are opposite vertices of a square and the diagonal length is $d$, then the side length is $d/\sqrt 2$, so the area is
$$\frac{d^2}{2}.$$
The entire problem becomes:
\mathbb E[\text{area}] = \frac12 \cdot \mathbb E\text{squared distance be