• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 21st, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <algorithm>
2. #include <iostream>
3. #include <vector>
4. #include <queue>
5.
6. using namespace std;
7.
8. typedef int64_t ll;
9.
10. struct Point {
11.     ll x, y;
12.
13.     Point(ll x = 0, ll y = 0)
14.         : x(x), y(y) {}
15.
16.     Point operator+ (Point other) {
17.         return Point(x + other.x, y + other.y);
18.     }
19.
20.     Point operator- (Point other) {
21.         return Point(x - other.x, y - other.y);
22.     }
23.
24.     ll operator% (Point other) {
25.         return x * other.x + y * other.y;
26.     }
27.
28.     ll operator* (Point other) {
29.         return x * other.y - y * other.x;
30.     }
31. };
32.
33. struct Line {
34.     ll a, b, c;
35.
36.     Line(ll a = 0, ll b = 0, ll c = 0)
37.         : a(a), b(b), c(c) {}
38.
39.     ll get(Point p) {
40.         return p.x * a + p.y * b + c;
41.     }
42. };
43.
44. struct Polygon {
45.     vector<Point> polygon;
46.
47.     Polygon() {}
48.
49.     Polygon(vector<Point>& a) {
50.         Point p = a[0];
51.         for (auto i : a) {
52.             if (i.y < p.y || (i.y == p.y && p.x > i.x)) {
53.                 p = i;
54.             }
55.         }
56.         sort(a.begin(), a.end(), [p](Point a, Point b) {
57.             if ((a - p) * (b - p) != 0) {
58.                 return (a - p) * (b - p) > 0;
59.             }
60.             return (a - p) % (a - p) < (b - p) % (b - p);
61.         });
62.         ll ptr = 0;
63.         for (auto i : a) {
64.             while (ptr >= 2 && (polygon[ptr - 1] - polygon[ptr - 2]) * (i - polygon[ptr - 2]) <= 0) {
65.                 --ptr;
66.                 polygon.pop_back();
67.             }
68.             polygon.emplace_back(i);
69.             ++ptr;
70.         }
71.         polygon.emplace_back(polygon[0]);
72.     }
73.
74.     bool check(Line line) {
75.         if (polygon.empty()) {
76.             return true;
77.         }
78.         ll left = 0;
79.         ll right = polygon.size();
80.         Point p = Point(-line.b, line.a);
81.         while (right - left > 1) {
82.             ll mid = (left + right) / 2;
83.             Point v = polygon[mid] - polygon[mid - 1];
84.             if (v * p >= 0) {
85.                 left = mid;
86.             }
87.             else {
88.                 right = mid;
89.             }
90.         }
91.         ll id1 = left;
92.         left = 0;
93.         right = polygon.size();
94.         p = Point(line.b, -line.a);
95.         while (right - left > 1) {
96.             ll mid = (left + right) / 2;
97.             Point v = polygon[mid] - polygon[mid - 1];
98.             if (v * p >= 0) {
99.                 left = mid;
100.             }
101.             else {
102.                 right = mid;
103.             }
104.         }
105.         ll id2 = left;
106.         ll mn = min(line.get(polygon[id1]), line.get(polygon[id2]));
107.         ll mx = max(line.get(polygon[id1]), line.get(polygon[id2]));
108.         return mn > 0 || mx < 0;
109.     }
110. };
111.
112. int main() {
113.     ll n, m;
114.     cin >> n >> m;
115.     vector<Line> a(n);
116.     for (ll i = 0; i < n; ++i) {
117.         cin >> a[i].a >> a[i].b >> a[i].c;
118.     }
119.     vector<Point> b(m);
120.     for (ll i = 0; i < m; ++i) {
121.         cin >> b[i].x >> b[i].y;
122.     }
123.     Polygon polygon(b);
124.     vector<ll> result;
125.     for (ll i = 0; i < n; ++i) {
126.         if (!polygon.check(a[i])) {
127.             result.emplace_back(i + 1);
128.         }
129.     }
130.     cout << result.size() << endl;
131.     for (ll i : result) {
132.         cout << i << " ";
133.     }
134.     return 0;
135. }
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