Theodore Roosevelt#2299

Theodore Roosevelt (Editorial)

Consider the problem of determining whether a point belongs to a convex polygon.

Suppose the vertices of the polygon are given in counterclockwise order: $p_{1}, p_{2}, ..., p_{n}$ p_1, p_2, ..., p_n. Fix the vertex $p_{1}$ p_1. Then all other vertices are ordered around it by polar angle.

Draw rays from point $p_{1}$ p_1 through the remaining vertices (i.e., the diagonals of the polygon). We can now apply binary search to find an edge $p_{i} p_{i + 1}$ p_ip_{i+1} such that the orientations of the triples of points $p_{1} p_{i} q$ p_1p_iq and $p_{1} p_{i + 1} q$ p_1p_{i+1}q are different.

Thus, we determine the sector (triangle) in which the point $q$ may lie.

After the angle $p_{i} p_{1} p_{i + 1}$ p_ip_1p_{i+1} containing the point $q$ is found, we can check in constant time whether the points $p_{1}$ p_1 and $q$ lie on the same side of the line $p_{i} p_{i + 1}$ p_ip_{i+1}. For this, the orientation of the triple $p_{i} p_{i + 1} q$ p_ip_{i+1}q must be left (since the orientation of $p_{i} p_{i + 1} p_{1}$ p_ip_{i+1}p_1 is left, as the polygon vertices are given in counterclockwise order).

At the beginning of the algorithm, it is also necessary to check boundary cases: if the orientation of the triple $p_{1} p_{n} q$ p_1p_nq is left or the orientation of the triple $p_{1} p_{2} q$ p_1p_2q is right, then the point $q$ lies outside the polygon.

Turn direction. Consider moving from point $А$ to point $В$ , and then from $В$ to point $С$ . The turn is considered left (counterclockwise) if the vector (pseudo-scalar) product $A B \times B C > 0$ AB \times BC > 0, and right if $A B \times B C < 0$ AB \times BC < 0.

Algorithm implementation

Let us define a $P o in t$ structure and an array of points.

#define MAX 100001
struct Point
{
  long long x, y;
  Point(long long x = 0, long long y = 0) : x(x), y(y) {}
};
Point p[MAX];

C++

The function angle determines whether the turn made when moving through points $А, B, С$ А, B, С is left or right. To do this, we calculate the corresponding vectors:

A B = (b . x - a . x, b . y - a . y) B C = (c . x - b . x, c . y - b . y)

AB = (b.x - a.x, b.y - a.y) \\ BC = (c.x - b.x, c.y - b.y)

The pseudo-scalar (cross) product of $A B \times B C$ AB \times BC is

b . x - a . x c . x - b . x b . y - a . y c . y - b . y = (b . x - a . x) \cdot (c . y - b . y) - (b . y - a . y) \cdot (c . x - b . x)

\begin{vmatrix} b.x - a.x & b.y - a.y \\ c.x - b.x & c.y - b.y \end{vmatrix} = (b.x - a.x)\cdot(c.y - b.y) - (b.y - a.y)\cdot(c.x - b.x)

The sign of this expression determines the direction of the turn:

Positive value — left turn;
Negative value — right turn;

int angle(Point a, Point b, Point c)
{
  long long q = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
  return (q > 0) - (q < 0); // sgn(q)
}

The function inside returns $t r u e$ if the point $q$ lies inside the polygon.

bool inside(Point q)
{

We choose the first vertex of the polygon as the base.

  Point a = p[1];

If the orientation of the triple $p_{1} p_{n} q$ p_1p_nq is left, or the orientation of the triple $p_{1} p_{2} q$ p_1p_2q is right, then the point $q$ lies outside the angle $p_{n} p_{1} p_{2}$ p_np_1p_2, and therefore outside the polygon.

  if (angle(a, p[2], q) < 0 || angle(a, p[n], q) > 0) return false;

Perform a binary search on the interval $[l; r] = [2; n]$ [l; r] = [2; n]. We look for points $p_{l}$ p_l and $p_{r} (r = l + 1)$ p_r~(r = l + 1) such that the point $q$ lies inside the angle $p_{l} p_{1} p_{r}$ p_lp_1p_r.

  int l = 2, r = n, m;
  while (l + 1 < r)
  {
    m = (l + r) / 2;
    if (angle(a, p[m], q) < 0)
      r = m;
    else
      l = m;
  }
  return angle(p[l], p[r], q) >= 0;
}

C++

The main part of the program. Read the input data.

scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++)
{
  scanf("%lld %lld", &x, &y);
  p[i] = Point(x, y);
}

Compute the number of points that lie inside the polygon.

res = 0;
for (int i = 1; i <= m; ++i)
{
  scanf("%lld %lld", &x, &y);
  if (inside(Point(x, y))) res++;
}

Print the answer.

if (res < k) puts("NO"); else puts("YES");