By scanning on a plane, the problem can be solved in a total of \(O((Q+N)\log(Q+N))\) or \(O(N+Q\log Q)\) time.

Figure: image of scanning

For a fixed \(x\)-coordinate, one can determine if a point is on \(S\) by comparing it with at most two edges of \(S\). By sorting in ascending order of their \(x\) coordinates, one can easily find two edges to compare.

Depending on implementation, extra caution may be required on the edges parallel to the \(y\) axis.

writer’s solution (C++)

How to compare a point and a segment

In order to compare a point and a line (segment), it is common in competitive programming to use inner and outer products. Here, for two vectors \(u\) and \(v\), we denote by \(u\cdot v\) their inner product and by \(u\times v \) their outer product.

For a segment \(PQ\) and a point \(R\):

• If \(PQ\times PR>0\), point \(R\) is in the left hand side when standing at \(P\) and looking at \(Q\).
• If \(PQ\times PR>0\), point \(R\) is in the right hand side when standing at \(P\) and looking at \(Q\).
• If \(PQ \times PR =0 \), point \(R\) is on line \(PQ\).
  • If \(PQ\cdot PR<0\), point \(R\) is on the line obtained by elongating segment \(PQ\) toward \(P\).
  • If \(0\leq PQ\cdot PR \leq PQ \cdot PQ\), point \(R\) is on segment \(PQ\).
  • If \(PQ\cdot PR > PQ \cdot PQ\), point \(R\) is on the line obtained by elongating segment \(PQ\) toward \(Q\).

We often use this method because it has no errors. While the computations on floating point numbers may have errors, computing the inner and outer product can be done within integers as long as the coordinates are integers, so we don’t have to care about the errors.

About outer product

Definition: For two vectors \(a\) and \(b\) in a three-dimensional space, their outer product \(a\times b\) is defined to be the vector that is perpendicular to bot h \(a\) and \(b\), has a direction given in the right-handed rule (see the figure), and with the magnitude equal to the parallelogram spanned by \(a\) and \(b\).

(Figure quoted from Wikipedia)

The property of outer product:
\((a_1,a_2,a_3)\times(b_1,b_2,b_3)=(a_2b_3-a_3b_2,a_3b_1-a_1b_3,a_1b_2-a_2b_1)\).

The “outer product” of two-dimensional vectors: For two \(2\)-dimensional vectors \(a=(a_1,a_2),b=(b_1,b_2)\), the signed area of the parallelogram spanned by the two vectors, \(a_1b_2-a_2b_1\), is defined to be their outer product.
This is the third component of \((a_1,a_2,0)\times(b_1,b_2,0)=(0,0,a_1b_2-a_2b_1)\), the outer product of two \(3\)-dimensional vectors.

Note that the “outer product” for two-dimensional vectors is a term conventionally used in the programming field, and not common in the mathematical field.

About inner product

Definition:
For two vectors \((a_1,\ldots.a_n)\) and \((b_1,\ldots,b_n)\) in an \(n\)-dimensional space, their (standard) inner product \(a\cdot b\) is defined as the value \( a_1b_1+a_2b_2+\ldots+a_nb_n\).

The property of inner product: The inner product of two vectors \(a\) and \(b\) equals the directed magnitude of the projection of \(b\) onto \(a\) multiplied by the magnitude of \(b\).