Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.57 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. #include <iomanip>
  5. #include <algorithm>
  6.  
  7.  
  8. double eps = 0.000001;
  9.  
  10. struct pt
  11. {
  12. double x;
  13. double y;
  14. };
  15.  
  16. double sq (pt & a, pt & b, pt & c) {
  17. return a.x*1ll*(b.y-c.y) + b.x*1ll*(c.y-a.y) + c.x*1ll*(a.y-b.y);
  18. }
  19.  
  20. struct ang{
  21. double x;
  22. double y;
  23. };
  24.  
  25. double lenVec(double a, double b)
  26. {
  27. return sqrt((double)a * a + (double)b * b);
  28. }
  29.  
  30. bool eq(double a, double b)
  31. {
  32. if (abs(a - b) < eps)
  33. {
  34. return true;
  35. }
  36. return false;
  37. }
  38.  
  39. double scal(double x1, double y1, double x2, double y2)
  40. {
  41. return x1 * x2 + y1 * y2;
  42. }
  43.  
  44. bool operator < (const ang &a, const ang &b)
  45. {
  46. if (a.x == 0 && b.x == 0)
  47. return a.x < b.x;
  48.  
  49. return a.y * b.x > a.x * b.y;
  50. }
  51.  
  52. int main()
  53. {
  54. int n, m, k;
  55. std::cin >> n >> m >> k;
  56. std::vector<pt> p(n);
  57. int cnt_in = 0;
  58. int zero_id = 0;
  59. for (int i = 0; i < n; ++i)
  60. {
  61. //std::cout << "kek " << i << std::endl;
  62. std::cin >> p[i].x >> p[i].y;
  63. if (p[i].x < p[zero_id].x || (p[i].x == p[zero_id].x && p[i].y < p[zero_id].y))
  64. {
  65. zero_id = i;
  66. }
  67. }
  68.  
  69. pt zero = p[zero_id];
  70. std::rotate (std::begin(p), std::begin(p) + zero_id, std::end(p));
  71. p.erase(p.begin());
  72. --n;
  73. //std::cout << "kek" << std::endl;
  74. std::vector<ang> a(n);
  75. for (int i = 0; i < n; ++i)
  76. {
  77. a[i] = {p[i].y - zero.y, p[i].x - zero.x};
  78. if (a[i].x == 0)
  79. {
  80. a[i].y = a[i].y < 0 ? -1 : 1;
  81. }
  82. }
  83. //std::cout << "kek" << std::endl;
  84. for (int i = 0; i < m; ++i)
  85. {
  86. pt q;
  87. std::cin >> q.x >> q.y;
  88. bool in = false;
  89. if (q.x >= zero.x)
  90. {
  91. if (eq(q.x, zero.x) && eq(q.y, zero.y))
  92. {
  93. in = true;
  94. }
  95. else
  96. {
  97. ang my = {q.y - zero.y, q.x - zero.x};
  98. if (my.x == 0)
  99. my.y = my.y < 0 ? -1 : 1;
  100. std::vector<ang>::iterator it = std::upper_bound(std::begin(a), std::end(a), my);
  101. if (it == std::end(a) && my.x == a[n - 1].x && my.y == a[n - 1].y)
  102. it = std::end(a) - 1;
  103. if (it != std::end(a) && it != std::begin(a))
  104. {
  105. int p1 = int (it - a.begin());
  106. if (sq(p[p1], p[p1 - 1], q) <= 0)
  107. in = true;
  108. }
  109. }
  110.  
  111. }
  112. if (in) cnt_in++;
  113. }
  114.  
  115. if (cnt_in >= k) std::cout << "YES";
  116. else std::cout << "NO";
  117.  
  118.  
  119.  
  120. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement