Solution

In order to determine if a point is inside a polygon, we can imagine a ray being cast from that point towards any direction. Resulting in three possible scenarios:

1. If the ray intersects with odd number of edges, then the point is inside.
2. If the ray intersects with even number of edges, then the point is outside.
3. If the origin point is on a line segment, then the point is on the edge.

This algorithm is known as the Ray Casting Algorithm.

Line segment & Line segment intersection

Given two line segments $L_1 = (p_1,p_2)$ and $L_2 = (p_3,p_4)$, how can we efficiently check if they intersect each other? We will first have to use a concept from linear algebra called the determinant.

We will define the determinant of two vectors as $\times$. Given two vectors $\vec{a}=\langle x_1,y_1 \rangle$ and $\vec{b}=\langle x_2,y_2 \rangle$. If $\vec{a}\times\vec{b}$ gives a positive area then $\vec{b}$ points to the left of $\vec{a}$, if it gives a negative area then $\vec{b}$ points to the right of $\vec{a}$, and if it gives a zero area then $\vec{b}$ and $\vec{a}$ are parallel.

To check if $L_1$ and $L_2$ intersect with each other, is equal to checking if $L_2$ intersects with the line from line segment $L_1$, and checking if $L_1$ intersects with the line from line segment $L_2$. For the first of two condition to be true, $p_3$ and $p_4$ from $L_2$ must be on the opposite directions of $L_1$. To define this mathematically, let

The condition will be true if and only if $\vec{a}\times\vec{b_1} \neq \vec{a}\times\vec{b_2}$. Verifying the second of the two cases is equivalent to the procedure above, except $p_1$ and $p_2$ are switched with $p_3$ and $p_4$.

As all geometry problem go, edge cases are a must. One edge case one might consider in our method above is that if both $\vec{a}\times\vec{b_1}$ and $\vec{a}\times\vec{b_2}$ are equal and are equal to 0, then they can still intersect as long as they overlap with each other. But let me let you in on a secret, due to the way this problem is structured, all vertices are on lattice points, meaning that they have whole numbers as coordinates. And since one of the $L$ is customizable (we get to pick the point the point cast its ray at), we can just set its coordinate to $(\infty,1)$. This way, the ray will have a slope of close to $0$, successfully avoiding all possible lattice point intersections. One trick to rule all the edge cases!

Implementation

Time Complexity: $\mathcal O(NM)$

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Point {
	ll x, y;
};

// Compute the determinant of two vectors (p1,p2) and (p3,p4)
ll det(Point p1, Point p2, Point p3, Point p4) {