Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /// @author s_k_a_r_a
- #include <bits/stdc++.h>
- #ifndef Local
- #define debug(...) 1337
- #define endl '\n'
- #endif
- using namespace std;
- #define int long long
- typedef long long ll;
- typedef long double ld;
- using str = string;
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define sz(x) (int)(x).size()
- template <typename T, typename U>
- bool smin(T& a, U b) {
- if (a > b) {
- a = b;
- return true;
- }
- return false;
- }
- template <typename T, typename U>
- bool smax(T& a, U b) {
- if (a < b) {
- a = b;
- return true;
- }
- return false;
- }
- #define type int
- const double eps = 1e-7;
- type sqr(type x) {
- return x * x;
- }
- int sign(double a, double b = 0) {
- if (a - b > eps)
- return 1;
- if (b - a > eps)
- return -1;
- return 0;
- }
- struct point {
- type x = 0, y = 0;
- point() = default;
- point(type x, type y) : x(x), y(y) {}
- point operator-(point t) const {
- return {x - t.x, y - t.y};
- }
- point operator+(point t) const {
- return {x + t.x, y + t.y};
- }
- type operator*(point t) const {
- return x * t.x + y * t.y;
- }
- type operator%(point t) const {
- return x * t.y - y * t.x;
- }
- point operator*(type t) const {
- return {x * t, y * t};
- }
- type dist2(point t) const {
- return sqr(x - t.x) + sqr(y - t.y);
- }
- double dist(point t) const {
- return sqrt(dist2(t));
- }
- type len2() const {
- return dist2({0, 0});
- }
- double len() const {
- return sqrt(len2());
- }
- };
- pair<double, double> lineToLine(point a, point da, point b, point db) {
- double n = (double)((b - a) % db) / (double)(da % db);
- double m = (double)((b - a) % db) / (double)(da % db);
- return {n, m};
- }
- vector<point> graham(vector<point> v) {
- point s = *min_element(all(v), [](auto a, auto b) { return sign(a.y, b.y) == -1 || (!sign(a.y, b.y) && sign(a.x, b.x) == -1); });
- sort(all(v), [&](auto a, auto b) {
- point sa = a - s;
- point sb = b - s;
- return sign(sa % sb) == 1 || (!sign(sa % sb) && sa.len2() < sb.len2());
- });
- vector<point> hull;
- for (int i = 0; i < sz(v); ++i) {
- point t = v[i];
- while (sz(hull) >= 2) {
- point c = t - hull.back();
- point p = hull.back() - hull[sz(hull) - 2];
- if (sign(p % c) != 1)
- hull.pop_back();
- else
- break;
- }
- hull.push_back(t);
- }
- return hull;
- }
- struct Line {
- type a = 0, b = 0, c = 0;
- Line() = default;
- Line(type a, type b, type c) : a(a), b(b), c(c) {}
- };
- bool lessByAngle(point a, point b) {
- if (sign(a.y) * sign(b.y) == 1 || (sign(a.y) * sign(b.y) == 0 && sign(a.x) * sign(b.y) != -1)) {
- if (a % b == 0 && sign(a.x) * sign(b.x) == -1)
- return a.x > b.x;
- return a % b > 0;
- }
- if (sign(b.y) == -1)
- return true;
- return false;
- }
- void solve() {
- int n, m;
- cin >> n >> m;
- vector<Line> lns(n);
- for (auto& [a, b, c] : lns)
- cin >> a >> b >> c;
- vector<point> h(m);
- for (auto& [x, y] : h)
- cin >> x >> y;
- h = graham(h);
- vector<int> ans;
- for (int t = 1; auto& [a, b, c] : lns) {
- int i = 0, j = 0;
- if (sz(h) != 1) {
- if (sz(h) == 2)
- j = 1;
- else {
- if (lessByAngle(h[1] - h[0], {-b, a})) {
- int l = 0;
- i = sz(h) - 1;
- while (i - l > 1) {
- int mid = (l + i) / 2;
- if (lessByAngle(h[mid + 1] - h[mid], {-b, a}) && (h[mid + 1] - h[mid]) % point(-b, a) != 0)
- l = mid;
- else
- i = mid;
- }
- }
- j = 0;
- if (lessByAngle(h[1] - h[0], {b, -a})) {
- int l = 0;
- j = sz(h) - 1;
- while (j - l > 1) {
- int mid = (l + j) / 2;
- if (lessByAngle(h[mid + 1] - h[mid], {b, -a}) && (h[mid + 1] - h[mid]) % point(b, -a) != 0)
- l = mid;
- else
- j = mid;
- }
- }
- }
- }
- if (sign(a * h[i].x + b * h[i].y + c) * sign(a * h[j].x + b * h[j].y + c) <= 0)
- ans.push_back(t);
- ++t;
- }
- cout << sz(ans) << endl;
- for (auto& i : ans)
- cout << i << ' ';
- cout << endl;
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int tt = 1;
- // cin >> tt;
- while (tt--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement