When discussing this exam question in today's revision lecture, there was a mistake in analysing the required slackness.

Stage 1 (computing the convex hull of the red points) requires slackness n >= p^3 (due to the sorting subroutine), not n >= p^2 as was written on the board.

Stage 2 (computing the signed area for each edge of the red convex hull with the blue point) requires slackness n >= p^2, as discussed.

The overall slackness required is therefore n >= p^3, as determined by Stage 1.

The BSP cost is comp O(n log n / p), comm O(n / p), sync O(1) as discussed.