SHARE
TWEET

Untitled

a guest Sep 23rd, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top