• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
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.

Top