Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <math.h>
- #include <iomanip>
- #include <algorithm>
- double eps = 0.000001;
- struct pt
- {
- double x;
- double y;
- };
- double sq (pt & a, pt & b, pt & c) {
- return a.x*1ll*(b.y-c.y) + b.x*1ll*(c.y-a.y) + c.x*1ll*(a.y-b.y);
- }
- struct ang{
- double x;
- double y;
- };
- double lenVec(double a, double b)
- {
- return sqrt((double)a * a + (double)b * b);
- }
- bool eq(double a, double b)
- {
- if (abs(a - b) < eps)
- {
- return true;
- }
- return false;
- }
- double scal(double x1, double y1, double x2, double y2)
- {
- return x1 * x2 + y1 * y2;
- }
- bool operator < (const ang &a, const ang &b)
- {
- if (a.x == 0 && b.x == 0)
- return a.x < b.x;
- return a.y * b.x > a.x * b.y;
- }
- int main()
- {
- int n, m, k;
- std::cin >> n >> m >> k;
- std::vector<pt> p(n);
- int cnt_in = 0;
- int zero_id = 0;
- for (int i = 0; i < n; ++i)
- {
- //std::cout << "kek " << i << std::endl;
- std::cin >> p[i].x >> p[i].y;
- if (p[i].x < p[zero_id].x || (p[i].x == p[zero_id].x && p[i].y < p[zero_id].y))
- {
- zero_id = i;
- }
- }
- pt zero = p[zero_id];
- std::rotate (std::begin(p), std::begin(p) + zero_id, std::end(p));
- p.erase(p.begin());
- --n;
- //std::cout << "kek" << std::endl;
- std::vector<ang> a(n);
- for (int i = 0; i < n; ++i)
- {
- a[i] = {p[i].y - zero.y, p[i].x - zero.x};
- if (a[i].x == 0)
- {
- a[i].y = a[i].y < 0 ? -1 : 1;
- }
- }
- //std::cout << "kek" << std::endl;
- for (int i = 0; i < m; ++i)
- {
- pt q;
- std::cin >> q.x >> q.y;
- bool in = false;
- if (q.x >= zero.x)
- {
- if (eq(q.x, zero.x) && eq(q.y, zero.y))
- {
- in = true;
- }
- else
- {
- ang my = {q.y - zero.y, q.x - zero.x};
- if (my.x == 0)
- my.y = my.y < 0 ? -1 : 1;
- std::vector<ang>::iterator it = std::upper_bound(std::begin(a), std::end(a), my);
- if (it == std::end(a) && my.x == a[n - 1].x && my.y == a[n - 1].y)
- it = std::end(a) - 1;
- if (it != std::end(a) && it != std::begin(a))
- {
- int p1 = int (it - a.begin());
- if (sq(p[p1], p[p1 - 1], q) <= 0)
- in = true;
- }
- }
- }
- if (in) cnt_in++;
- }
- if (cnt_in >= k) std::cout << "YES";
- else std::cout << "NO";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement