<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

253. Theodore Roosevelt
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Danger! Sudden attack on Russia! These are Americans "again", but this time they are serious. Giant aircraft-carrier "Theodore Roosevelt" is entering the Baltic Sea. At one o'clock American aircraft launched from the carrier bombed Petrozavodsk.
At three o'clock we detected the location of "Theodore Roosevelt". In a moment Russian fighters Mig-29 took off into the night air to inflict the crushing strike against the carrier. Using top secret military satellite "Raduga-1" we detected the exact region where the carrier was located - the convex polygon. The fighters launched M rockets and ground forces detected the coordinates of their explosions.
You are an indispensable engineer of Russian military forces, and you were waken up by the phone call at four o'clock. They command you to arrive to headquarters for the most important task - detect whether "Theodore Roosevelt" was destroyed or not! You are given all information: the coordinates of vertices of the region polygon and the coordinates of the explosions.
It was computed that at least K rockets should have hit the detected region to destroy the carrier. Commander ordered you to complete the work till five o'clock, so you must hurry.

Input
The first line of input contains three integers N, M and K (3<=N<=10^5, 0<=K<=M<=10^5). The following N lines contain coordinates of polygon vertices in counter-clockwise order. And then last M lines contain coordinates of rockets explosions. Is is guaranteed that all coordinates are integer numbers not exceeding 10^9 by their absolute value.

Output
Output "YES" (without quotes) if "Theodore Roosevelt" was destroyed, or "NO" (without quotes) in the other case.

Sample test(s)

Input
5 4 2
1 -1
1 2
0 4
-1 2
-1 -1
-2 -1
1 -1
0 1
2 3

Output
YES
Author:	Dmitry Filippov (DEF)
Resource:	Petrozavodsk Summer Training Sessions 2004
Date:	August 25, 2004

<|response|>
1. Abridged problem statement
Given a convex polygon of N vertices in counter-clockwise order, and M query points, determine how many query points lie inside or on the boundary of the polygon. If at least K points are inside or on the polygon, output "YES", otherwise "NO". Constraints: 3 ≤ N ≤ 10^5, 0 ≤ K ≤ M ≤ 10^5, coordinates are integers with absolute value ≤ 10^9.

2. Key observations
- A general point-in-polygon test is O(N) per query, too slow for N, M up to 10^5.
- For a **convex** polygon, we can answer each query in O(log N) by "fan-triangulating" from one fixed vertex.
- Choose one polygon vertex P0 (e.g. the lexicographically minimum (x,y)). The other vertices, in CCW order around P0, form a fan of triangles (P0, Pi, Pi+1).
- To test a point Q:
  1. Binary-search to find the wedge [P0, P_i, P_{i+1}] that could contain Q.
  2. Finally check with cross products that Q lies inside or on triangle (P0, P_i, P_{i+1}).

3. Full solution approach
Step A. Read N, M, K. Read polygon vertices in CCW order. Read M query points.
Step B. Find the lexicographically smallest vertex P0 among the N points and sort the remaining vertices by polar angle around it (this is the fan in CCW order).
Step C. Define orientation (cross product) function ccw(A,B,C) = sign of (B−A)×(C−A); it is +1 if A→B→C makes a CCW turn, −1 if CW, 0 if collinear.
Step D. For each query Q binary-search on the sorted vertices: keep [l, r] and while r−l>1 set m=(l+r)/2; if ccw(P0, vertex[m], Q) ≥ 0 set l=m else r=m. After the loop Q lies between rays P0→vertex[l] and P0→vertex[r].
Step E. Check if Q is inside triangle (P0, vertex[l], vertex[r]) with three orientation tests (all nonnegative or all nonpositive). If so, count it as inside or on boundary.
Step F. If the total count ≥ K, print "YES", else "NO".

Time complexity: O(N log N + M log N). Memory: O(N + M).

4. C++ implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

using coord_t = double;

struct Point {
    coord_t x, y;
    Point(coord_t x = 0, coord_t y = 0) : x(x), y(y) {}

    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    Point operator*(coord_t c) const { return Point(x * c, y * c); }
    Point operator/(coord_t c) const { return Point(x / c, y / c); }

    coord_t operator*(const Point& p) const { return x * p.x + y * p.y; }
    coord_t operator^(const Point& p) const { return x * p.y - y * p.x; }

    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
    bool operator!=(const Point& p) const { return x != p.x || y != p.y; }
    bool operator<(const Point& p) const {
        return x != p.x ? x < p.x : y < p.y;
    }

    bool operator>(const Point& p) const {
        return x != p.x ? x > p.x : y > p.y;
    }

    bool operator<=(const Point& p) const {
        return x != p.x ? x < p.x : y <= p.y;
    }

    bool operator>=(const Point& p) const {
        return x != p.x ? x > p.x : y >= p.y;
    }

    coord_t norm2() const { return x * x + y * y; }
    double norm() const { return sqrt(norm2()); }
    double angle() const { return atan2(y, x); }

    Point rotate(double a) const {
        return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
    }

    Point perp() const { return Point(-y, x); }
    Point unit() const { return *this / norm(); }
    Point normal() const { return perp().unit(); }
    Point project(const Point& p) const {
        return *this * (*this * p) / norm2();
    }

    Point reflect(const Point& p) const {
        return *this * 2 * (*this * p) / norm2() - p;
    }

    friend ostream& operator<<(ostream& os, const Point& p) {
        return os << p.x << ' ' << p.y;
    }

    friend istream& operator>>(istream& is, Point& p) {
        return is >> p.x >> p.y;
    }

    friend int ccw(const Point& a, const Point& b, const Point& c) {
        coord_t v = (b - a) ^ (c - a);
        if(v > 0) {
            return 1;
        } else if(v < 0) {
            return -1;
        } else {
            return 0;
        }
    }

    friend bool point_in_triangle(
        const Point& a, const Point& b, const Point& c, const Point& p
    ) {
        int d1 = ccw(a, b, p);
        int d2 = ccw(b, c, p);
        int d3 = ccw(c, a, p);
        return (d1 >= 0 && d2 >= 0 && d3 >= 0) ||
               (d1 <= 0 && d2 <= 0 && d3 <= 0);
    }
};

class Polygon {
  public:
    vector<Point> points;

    Polygon() {}
    Polygon(const vector<Point>& points) : points(points) {}

    int size() const { return points.size(); }

    coord_t area() const {
        coord_t a = 0;
        for(int i = 0; i < size(); i++) {
            a += points[i] ^ points[(i + 1) % size()];
        }

        return a / 2.0;
    }
};

class PointInConvexPolygon {
  private:
    Point min_point;
    vector<Point> points_by_angle;

    void prepare() {
        points_by_angle = polygon.points;
        vector<Point>::iterator min_point_it =
            min_element(points_by_angle.begin(), points_by_angle.end());
        min_point = *min_point_it;

        points_by_angle.erase(min_point_it);
        sort(
            points_by_angle.begin(), points_by_angle.end(),
            [&](const Point& a, const Point& b) {
                int d = ccw(min_point, a, b);
                if(d != 0) {
                    return d > 0;
                }

                return (a - min_point).norm2() < (b - min_point).norm2();
            }
        );
    }

  public:
    Polygon polygon;
    PointInConvexPolygon(const Polygon& polygon) : polygon(polygon) {
        prepare();
    }

    bool contains(const Point& p) const {
        int l = 0, r = (int)points_by_angle.size() - 1;
        while(r - l > 1) {
            int m = (l + r) / 2;
            if(ccw(min_point, points_by_angle[m], p) >= 0) {
                l = m;
            } else {
                r = m;
            }
        }

        return point_in_triangle(
            min_point, points_by_angle[l], points_by_angle[r], p
        );
    }
};

int n, m, k;
vector<Point> points;
vector<Point> queries;

void read() {
    cin >> n >> m >> k;
    points.resize(n);
    queries.resize(m);
    cin >> points >> queries;
}

void solve() {
    // The polygon is convex and given in counter-clockwise order. We anchor at
    // its lexicographically smallest vertex and sort the remaining vertices by
    // polar angle around it, fanning the polygon into triangles. For each query
    // explosion we binary search for the angular wedge it falls into: find the
    // sorted vertex m with the point still on the left of ray (anchor, m), which
    // gives the bounding triangle (anchor, vertex[l], vertex[r]); the point is
    // inside the polygon iff it lies in that triangle (boundary counts). We
    // count how many of the M explosions land inside and answer YES iff at least
    // K of them did.

    Polygon polygon(points);
    PointInConvexPolygon picp(polygon);

    int cnt_inside = 0;
    for(auto& q: queries) {
        cnt_inside += picp.contains(q);
    }

    if(cnt_inside >= k) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments
```python
import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))

    # Read polygon vertices
    poly = []
    for _ in range(N):
        x = int(next(it)); y = int(next(it))
        poly.append((x, y))

    # Read query points
    queries = []
    for _ in range(M):
        x = int(next(it)); y = int(next(it))
        queries.append((x, y))

    # Find lexicographically smallest vertex
    idx0 = min(range(N), key=lambda i: (poly[i][0], poly[i][1]))
    # Rotate so that idx0 is first
    pts = poly[idx0:] + poly[:idx0]
    P0 = pts[0]
    fan = pts[1:]    # list of N-1 points in CCW around P0

    # Cross product (B - A) × (C - A)
    def cross(A, B, C):
        return (B[0] - A[0]) * (C[1] - A[1]) - \
               (B[1] - A[1]) * (C[0] - A[0])

    # Check if Q in triangle A-B-C (including boundary)
    def in_triangle(A, B, C, Q):
        c1 = cross(A, B, Q)
        c2 = cross(B, C, Q)
        c3 = cross(C, A, Q)
        # all non-negative or all non-positive
        return (c1 >= 0 and c2 >= 0 and c3 >= 0) or \
               (c1 <= 0 and c2 <= 0 and c3 <= 0)

    cnt = 0
    for Q in queries:
        # Quick reject against the first and last rays
        if cross(P0, fan[0], Q) < 0:
            continue
        if cross(P0, fan[-1], Q) > 0:
            continue

        # Binary search to find wedge [P0, fan[L], fan[R]]
        L, R = 0, len(fan) - 1
        while R - L > 1:
            mid = (L + R) // 2
            if cross(P0, fan[mid], Q) >= 0:
                L = mid
            else:
                R = mid

        # Final triangle test
        if in_triangle(P0, fan[L], fan[R], Q):
            cnt += 1

    # Output result
    print("YES" if cnt >= K else "NO")

if __name__ == "__main__":
    main()
```
