Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*#pragma GCC optimize("Ofast,no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC optimize("fast-math")*/
- #include <iostream>
- #include <complex>
- #include <vector>
- #include <string>
- #include <algorithm>
- #include <cstdio>
- #include <numeric>
- #include <cstring>
- #include <ctime>
- #include <cstdlib>
- #include <set>
- #include <map>
- #include <unordered_map>
- #include <unordered_set>
- #include <list>
- #include <cmath>
- #include <bitset>
- #include <cassert>
- #include <queue>
- #include <stack>
- #include <deque>
- #include <random>
- using namespace std;
- #define pb push_back
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define Str(x) to_string(x)
- #define len(s) (int)s.size()
- #define int long long
- typedef long long ll;
- typedef long double lld;
- typedef string str;
- typedef unsigned long long ull;
- struct pt {
- int x, y;
- };
- struct ang {
- int a, b;
- };
- bool operator < (const ang & p, const ang & q) {
- if (p.b == 0 && q.b == 0)
- return p.a < q.a;
- return p.a * 1ll * q.b < p.b * 1ll * q.a;
- }
- long long 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);
- }
- pt vectr(pt a, pt b) {
- return {b.x - a.x, b.y - a.y};
- }
- int VP(pt a, pt b) {
- return a.x * b.y - a.y * b.x;
- }
- int S(pt a, pt b, pt c, pt p) {
- return abs(VP(vectr(p, a), vectr(p, b))) + abs(VP(vectr(p, a), vectr(p, c))) + abs(VP(vectr(p, b), vectr(p, c)));
- }
- main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int n, m, k;
- cin >> n >> m >> k;
- vector<pt> p (n);
- int zero_id = 0;
- for (int i=0; i<n; ++i) {
- 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];
- rotate (p.begin(), p.begin()+zero_id, p.end());
- p.erase (p.begin());
- --n;
- vector<ang> a (n);
- for (int i=0; i<n; ++i) {
- a[i].a = p[i].y - zero.y;
- a[i].b = p[i].x - zero.x;
- }
- int cnt = 0;
- for (int step = 0; step < m; step++) {
- pt q;
- cin >> q.x >> q.y;
- bool in = false;
- if (q.x >= zero.x)
- if (q.x == zero.x && q.y == zero.y)
- in = true;
- else {
- ang my = { q.y-zero.y, q.x-zero.x };
- vector<ang>::iterator it = upper_bound (a.begin(), a.end(), my);
- if (it == a.end() && my.a == a[n-1].a && my.b == a[n-1].b)
- it = a.end()-1;
- if (it != a.end() && it != a.begin()) {
- int p1 = it - a.begin();
- if (S(zero, p[p1], p[p1 - 1], q) == abs(VP(vectr(zero, p[p1]), vectr(zero, p[p1 - 1]))))
- in = true;
- }
- }
- cnt += in;
- }
- cout << (cnt >= k ? "YES" : "NO");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement