Let\'s say I have a 11x11 grid with a few points (around 8) marked in the grid.

ID: 657203 • Letter: L

Question

Let's say I have a 11x11 grid with a few points (around 8) marked in the grid. One of the points is in the center cell. Call it point P.

I choose a point other than P and connect it with a line segment to P. Call that point C1

I choose another point that is not C1 and connect it with a line segment to P. Call that point C2.

Now, if we extend the line segments out from P to the edges of the grid, then the grid will be split into two regions A and B.

How can I determine which of the remaining points are in A and B efficiently?

Hint: Instead of storing them as cartesian points, store them as polar coordinates (with a tiny drop of preprocessing).

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.