Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.07 KB | None | 0 0
  1. /*#pragma GCC optimize("Ofast,no-stack-protector")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #pragma GCC optimize("unroll-loops")
  4. #pragma GCC optimize("fast-math")*/
  5. #include <iostream>
  6. #include <complex>
  7. #include <vector>
  8. #include <string>
  9. #include <algorithm>
  10. #include <cstdio>
  11. #include <numeric>
  12. #include <cstring>
  13. #include <ctime>
  14. #include <cstdlib>
  15. #include <set>
  16. #include <map>
  17. #include <unordered_map>
  18. #include <unordered_set>
  19. #include <list>
  20. #include <cmath>
  21. #include <bitset>
  22. #include <cassert>
  23. #include <queue>
  24. #include <stack>
  25. #include <deque>
  26. #include <random>
  27.  
  28. using namespace std;
  29.  
  30. #define pb push_back
  31. #define all(x) x.begin(), x.end()
  32. #define rall(x) x.rbegin(), x.rend()
  33. #define Str(x) to_string(x)
  34. #define len(s) (int)s.size()
  35. #define int long long
  36. typedef long long ll;
  37. typedef long double lld;
  38. typedef string str;
  39. typedef unsigned long long ull;
  40.  
  41. struct pt {
  42. int x, y;
  43. };
  44.  
  45. struct ang {
  46. int a, b;
  47. };
  48.  
  49. bool operator < (const ang & p, const ang & q) {
  50. if (p.b == 0 && q.b == 0)
  51. return p.a < q.a;
  52. return p.a * 1ll * q.b < p.b * 1ll * q.a;
  53. }
  54.  
  55. long long sq (pt & a, pt & b, pt & c) {
  56. return a.x*1ll*(b.y-c.y) + b.x*1ll*(c.y-a.y) + c.x*1ll*(a.y-b.y);
  57. }
  58.  
  59. pt vectr(pt a, pt b) {
  60. return {b.x - a.x, b.y - a.y};
  61. }
  62.  
  63. int VP(pt a, pt b) {
  64. return a.x * b.y - a.y * b.x;
  65. }
  66.  
  67. int S(pt a, pt b, pt c, pt p) {
  68. 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)));
  69. }
  70.  
  71. main() {
  72. ios_base::sync_with_stdio(false);
  73. cin.tie(NULL);
  74. cout.tie(NULL);
  75. #ifdef LOCAL
  76. freopen("input.txt", "r", stdin);
  77. freopen("output.txt", "w", stdout);
  78. #endif
  79. int n, m, k;
  80. cin >> n >> m >> k;
  81. vector<pt> p (n);
  82. int zero_id = 0;
  83. for (int i=0; i<n; ++i) {
  84. cin >> p[i].x >> p[i].y;
  85. if (p[i].x < p[zero_id].x || p[i].x == p[zero_id].x && p[i].y < p[zero_id].y)
  86. zero_id = i;
  87. }
  88. pt zero = p[zero_id];
  89. rotate (p.begin(), p.begin()+zero_id, p.end());
  90. p.erase (p.begin());
  91. --n;
  92.  
  93. vector<ang> a (n);
  94. for (int i=0; i<n; ++i) {
  95. a[i].a = p[i].y - zero.y;
  96. a[i].b = p[i].x - zero.x;
  97. }
  98. int cnt = 0;
  99. for (int step = 0; step < m; step++) {
  100. pt q;
  101. cin >> q.x >> q.y;
  102. bool in = false;
  103. if (q.x >= zero.x)
  104. if (q.x == zero.x && q.y == zero.y)
  105. in = true;
  106. else {
  107. ang my = { q.y-zero.y, q.x-zero.x };
  108. vector<ang>::iterator it = upper_bound (a.begin(), a.end(), my);
  109. if (it == a.end() && my.a == a[n-1].a && my.b == a[n-1].b)
  110. it = a.end()-1;
  111. if (it != a.end() && it != a.begin()) {
  112. int p1 = it - a.begin();
  113. if (S(zero, p[p1], p[p1 - 1], q) == abs(VP(vectr(zero, p[p1]), vectr(zero, p[p1 - 1]))))
  114. in = true;
  115. }
  116. }
  117. cnt += in;
  118. }
  119. cout << (cnt >= k ? "YES" : "NO");
  120. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement