站外题求助

给定 $n\times m$ 的网格，在其中随机选择 $k$ 个格点，求凸包点数大小期望。

求优于 $O(n^2m^2)$ 做法。