TEAMBOOK Платные дороги

#include <bits/stdc++.h>
using ld = long double;
using ll = long long;
#define double ld
#define long ll
#define all(x) begin(x), end(x)
using namespace std;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());

int cmp(double a, double b) {
    const double EPS = 1e-9;
    if (abs(a - b) <= EPS) {
        return 0;
    } else if (a < b) {
        return -1;
    } else {
        return +1;
    }
}

struct Point {
    double x, y;
    Point(double a, double b) : x(a), y(b) {}
    Point() : Point(0, 0) {}
};
istream &operator>>(istream &in, Point &p) {
    int x, y;
    in >> x >> y;
    p.x = x;
    p.y = y;
    return in;
}
ostream &operator<<(ostream &out, Point p) {
    return out << p.x << " " << p.y;
}
ld operator%(Point a, Point b) {
    return a.x * b.y - a.y * b.x;
}
Point operator-(Point a, Point b) {
    return {a.x - b.x, a.y - b.y};
}
Point operator+(Point a, Point b) {
    return {a.x + b.x, a.y + b.y};
}
bool operator<(Point a, Point b) {
    if (cmp(a.x, b.x)) {
        return a.x < b.x;
    }
    return a.y < b.y;
}

int turn(Point a, Point b, Point c) {
    return cmp((b - a) % (c - a), 0);
}

const int N = 2e5;
int n, m, us = 0, ds = 0;
double lA[N], lB[N], lC[N];
Point p[N], u[N], d[N];
pair<double, Point> sorted[N];

Point findBorder(double x, double y) {
    double ang = atan2(-x, y);
    int i = (lower_bound(sorted, sorted + n, make_pair(ang, Point(0, 0))) - sorted) % n;
    return sorted[i].second;
}

bool fastQuery(double A, double B, double C) {
    Point a = findBorder(A, B);
    Point b = findBorder(-A, -B);
    int x = cmp(a.x * A + a.y * B + C, 0);
    int y = cmp(b.x * A + b.y * B + C, 0);
    return x * y <= 0;
}

bool slowQuery(double A, double B, double C) {
    bool le = false, gr = false;
    for (int i = 0; i < n; ++i) {
        int c = cmp(A * p[i].x + B * p[i].y + C, 0);
        if (c == 0) {
            return true;
        }
        if (c < 0) {
            le = true;
        } else {
            gr = true;
        }
    }
    return le && gr;
}

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#else
    assert(freopen("highways.in", "r", stdin));
    assert(freopen("highways.out", "w", stdout));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);

    cin >> m >> n;
    for (int i = 0; i < m; ++i) {
        cin >> lA[i] >> lB[i] >> lC[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }

    sort(p, p + n, [&](Point a, Point b) {
        int x = cmp(a.x, b.x);
        if (x) {
            return x < 0;
        }
        return cmp(a.y, b.y) < 0;
    });

    u[us++] = p[0];
    d[ds++] = p[0];
    for (int i = 1; i < n; ++i) {
        if (i == n - 1 || turn(p[0], p[i], p[n - 1]) < 0) {
            while (us >= 2 && turn(u[us - 2], u[us - 1], p[i]) >= 0) {
                --us;
            }
            u[us++] = p[i];
        }
        if (i == n - 1 || turn(p[0], p[i], p[n - 1]) > 0) {
            while (ds >= 2 && turn(d[ds - 2], d[ds - 1], p[i]) <= 0) {
                --ds;
            }
            d[ds++] = p[i];
        }
    }
    n = ds;
    copy(d, d + n, p);
    for (--us; us > 1; ) {
        p[n++] = u[--us];
    }
    p[n] = p[0];

    for (int i = 0; i < n; ++i) {
        Point v = p[i + 1] - p[i];
        sorted[i] = {atan2(v.y, v.x), p[i]};
    }
    sort(sorted, sorted + n);
    vector<int> answer;
    for (int qr = 0; qr < m; ++qr) {
        bool f = fastQuery(lA[qr], lB[qr], lC[qr]);
        if (f) {
            answer.push_back(qr + 1);
        }
    }
    cout << answer.size() << "\n";
    for (int e : answer) {
        cout << e << " ";
    }
    cout << "\n";

    return 0;
}