2299. Theodore Roosevelt

“Theodore Roosevelt” – the flagship of the Kukuland fleet. The sworn enemies of Kukuland, the Flat-Earthers, decided to destroy it. They learned that “Theodore Roosevelt” is represented by a convex polygon with  vertices, and the coordinates of all its vertices are known to them. Then they launched  ballistic missiles and recorded the coordinates of their explosion points. According to the calculations of the Flat-Earthers' headquarters, “Theodore Roosevelt” will be destroyed if at least k missiles hit it. Determine whether the Flat-Earthers managed to destroy the ship.

Input. The first line contains integers n, m and k (3 ≤ n ≤ 10⁵, 0 ≤ k ≤ m ≤ 10⁵). The next n lines contain the coordinates of the polygon vertices in counterclockwise order. The following m lines contain the coordinates of the explosion points. All coordinates are integers with absolute values not exceeding 10⁹.

Output. Print “YES” if at least k points lie inside the polygon, and “NO” otherwise.

Sample input	Sample output
5 4 2 1 -1 1 2 0 4 -1 2 -1 -1 -2 -1 1 -1 0 1 2 3	YES

SOLUTION

geometry + binary search

Algorithm analysis

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₁, p₂, …, p_n. Fix the vertex p₁. Then all other vertices are ordered around it by polar angle.

Draw rays from point p₁ through the remaining vertices (i.e., the diagonals of the polygon). We can now apply binary search to find an edge p_ip_i+1 such that the orientations of the triples of points p₁p_iq and p₁p_i+1q are different.

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

After the angle p_ip₁p_i+1 containing the point q is found, we can check in constant time whether the points p₁ and q lie on the same side of the line p_ip_i+1. For this, the orientation of the triple p_ip_i+1q must be left (since the orientation of p_ip_i+1p₁ 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₁p_nq is left or the orientation of the triple p₁p₂q 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 AB ´ BC > 0, and right if AB ´ BC < 0.

Algorithm implementation

Let us define a Point 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];

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

AB = (b.x – a.x, b.y – a.y)

BC = (c.x – b.x, c.y – b.y)

The pseudo-scalar (cross) product of AB ´ BC is

= (b.x – a.x) * (c.y – b.y) – (b.y – a.y) * (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 true 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₁p_nq is left, or the orientation of the triple p₁p₂q is right, then the point q lies outside the angle p_np₁p₂, 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]. We look for points p_l and p_r (r = l + 1) such that the point q lies inside the angle p_lp₁p_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;

}

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");