Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef int64_t ll;
- struct Point {
- ll x, y;
- Point(ll x = 0, ll y = 0)
- : x(x), y(y) {}
- Point operator+ (Point other) {
- return Point(x + other.x, y + other.y);
- }
- Point operator- (Point other) {
- return Point(x - other.x, y - other.y);
- }
- ll operator% (Point other) {
- return x * other.x + y * other.y;
- }
- ll operator* (Point other) {
- return x * other.y - y * other.x;
- }
- };
- struct Line {
- ll a, b, c;
- Line(ll a = 0, ll b = 0, ll c = 0)
- : a(a), b(b), c(c) {}
- ll get(Point p) {
- return p.x * a + p.y * b + c;
- }
- };
- struct Polygon {
- vector<Point> polygon;
- Polygon() {}
- Polygon(vector<Point>& a) {
- Point p = a[0];
- for (auto i : a) {
- if (i.y < p.y || (i.y == p.y && p.x > i.x)) {
- p = i;
- }
- }
- sort(a.begin(), a.end(), [p](Point a, Point b) {
- if ((a - p) * (b - p) != 0) {
- return (a - p) * (b - p) > 0;
- }
- return (a - p) % (a - p) < (b - p) % (b - p);
- });
- ll ptr = 0;
- for (auto i : a) {
- while (ptr >= 2 && (polygon[ptr - 1] - polygon[ptr - 2]) * (i - polygon[ptr - 2]) <= 0) {
- --ptr;
- polygon.pop_back();
- }
- polygon.emplace_back(i);
- ++ptr;
- }
- polygon.emplace_back(polygon[0]);
- }
- bool check(Line line) {
- if (polygon.empty()) {
- return true;
- }
- ll left = 0;
- ll right = polygon.size();
- Point p = Point(-line.b, line.a);
- while (right - left > 1) {
- ll mid = (left + right) / 2;
- Point v = polygon[mid] - polygon[mid - 1];
- if (v * p >= 0) {
- left = mid;
- }
- else {
- right = mid;
- }
- }
- ll id1 = left;
- left = 0;
- right = polygon.size();
- p = Point(line.b, -line.a);
- while (right - left > 1) {
- ll mid = (left + right) / 2;
- Point v = polygon[mid] - polygon[mid - 1];
- if (v * p >= 0) {
- left = mid;
- }
- else {
- right = mid;
- }
- }
- ll id2 = left;
- ll mn = min(line.get(polygon[id1]), line.get(polygon[id2]));
- ll mx = max(line.get(polygon[id1]), line.get(polygon[id2]));
- return mn > 0 || mx < 0;
- }
- };
- int main() {
- ll n, m;
- cin >> n >> m;
- vector<Line> a(n);
- for (ll i = 0; i < n; ++i) {
- cin >> a[i].a >> a[i].b >> a[i].c;
- }
- vector<Point> b(m);
- for (ll i = 0; i < m; ++i) {
- cin >> b[i].x >> b[i].y;
- }
- Polygon polygon(b);
- vector<ll> result;
- for (ll i = 0; i < n; ++i) {
- if (!polygon.check(a[i])) {
- result.emplace_back(i + 1);
- }
- }
- cout << result.size() << endl;
- for (ll i : result) {
- cout << i << " ";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement