Advertisement
skaram

Untitled

Dec 23rd, 2023
1,125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.88 KB | None | 0 0
  1. /// @author s_k_a_r_a
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #ifndef Local
  6. #define debug(...) 1337
  7. #define endl '\n'
  8. #endif
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16.  
  17. using str = string;
  18. #define all(x) (x).begin(), (x).end()
  19. #define rall(x) (x).rbegin(), (x).rend()
  20. #define sz(x) (int)(x).size()
  21. template <typename T, typename U>
  22. bool smin(T& a, U b) {
  23.     if (a > b) {
  24.         a = b;
  25.         return true;
  26.     }
  27.     return false;
  28. }
  29. template <typename T, typename U>
  30. bool smax(T& a, U b) {
  31.     if (a < b) {
  32.         a = b;
  33.         return true;
  34.     }
  35.     return false;
  36. }
  37.  
  38. #define type int
  39.  
  40. const double eps = 1e-7;
  41.  
  42. type sqr(type x) {
  43.     return x * x;
  44. }
  45.  
  46. int sign(double a, double b = 0) {
  47.     if (a - b > eps)
  48.         return 1;
  49.     if (b - a > eps)
  50.         return -1;
  51.     return 0;
  52. }
  53.  
  54. struct point {
  55.     type x = 0, y = 0;
  56.  
  57.     point() = default;
  58.  
  59.     point(type x, type y) : x(x), y(y) {}
  60.  
  61.     point operator-(point t) const {
  62.         return {x - t.x, y - t.y};
  63.     }
  64.  
  65.     point operator+(point t) const {
  66.         return {x + t.x, y + t.y};
  67.     }
  68.  
  69.     type operator*(point t) const {
  70.         return x * t.x + y * t.y;
  71.     }
  72.  
  73.     type operator%(point t) const {
  74.         return x * t.y - y * t.x;
  75.     }
  76.  
  77.     point operator*(type t) const {
  78.         return {x * t, y * t};
  79.     }
  80.  
  81.     type dist2(point t) const {
  82.         return sqr(x - t.x) + sqr(y - t.y);
  83.     }
  84.  
  85.     double dist(point t) const {
  86.         return sqrt(dist2(t));
  87.     }
  88.  
  89.     type len2() const {
  90.         return dist2({0, 0});
  91.     }
  92.  
  93.     double len() const {
  94.         return sqrt(len2());
  95.     }
  96. };
  97.  
  98. pair<double, double> lineToLine(point a, point da, point b, point db) {
  99.     double n = (double)((b - a) % db) / (double)(da % db);
  100.     double m = (double)((b - a) % db) / (double)(da % db);
  101.     return {n, m};
  102. }
  103.  
  104. vector<point> graham(vector<point> v) {
  105.     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); });
  106.     sort(all(v), [&](auto a, auto b) {
  107.         point sa = a - s;
  108.         point sb = b - s;
  109.         return sign(sa % sb) == 1 || (!sign(sa % sb) && sa.len2() < sb.len2());
  110.     });
  111.     vector<point> hull;
  112.     for (int i = 0; i < sz(v); ++i) {
  113.         point t = v[i];
  114.         while (sz(hull) >= 2) {
  115.             point c = t - hull.back();
  116.             point p = hull.back() - hull[sz(hull) - 2];
  117.             if (sign(p % c) != 1)
  118.                 hull.pop_back();
  119.             else
  120.                 break;
  121.         }
  122.         hull.push_back(t);
  123.     }
  124.     return hull;
  125. }
  126.  
  127. struct Line {
  128.     type a = 0, b = 0, c = 0;
  129.  
  130.     Line() = default;
  131.  
  132.     Line(type a, type b, type c) : a(a), b(b), c(c) {}
  133. };
  134.  
  135. bool lessByAngle(point a, point b) {
  136.     if (sign(a.y) * sign(b.y) == 1 || (sign(a.y) * sign(b.y) == 0 && sign(a.x) * sign(b.y) != -1)) {
  137.         if (a % b == 0 && sign(a.x) * sign(b.x) == -1)
  138.             return a.x > b.x;
  139.         return a % b > 0;
  140.     }
  141.     if (sign(b.y) == -1)
  142.         return true;
  143.     return false;
  144. }
  145.  
  146. void solve() {
  147.     int n, m;
  148.     cin >> n >> m;
  149.     vector<Line> lns(n);
  150.     for (auto& [a, b, c] : lns)
  151.         cin >> a >> b >> c;
  152.     vector<point> h(m);
  153.     for (auto& [x, y] : h)
  154.         cin >> x >> y;
  155.     h = graham(h);
  156.     vector<int> ans;
  157.     for (int t = 1; auto& [a, b, c] : lns) {
  158.         int i = 0, j = 0;
  159.         if (sz(h) != 1) {
  160.             if (sz(h) == 2)
  161.                 j = 1;
  162.             else {
  163.                 if (lessByAngle(h[1] - h[0], {-b, a})) {
  164.                     int l = 0;
  165.                     i = sz(h) - 1;
  166.                     while (i - l > 1) {
  167.                         int mid = (l + i) / 2;
  168.                         if (lessByAngle(h[mid + 1] - h[mid], {-b, a}) && (h[mid + 1] - h[mid]) % point(-b, a) != 0)
  169.                             l = mid;
  170.                         else
  171.                             i = mid;
  172.                     }
  173.                 }
  174.                 j = 0;
  175.                 if (lessByAngle(h[1] - h[0], {b, -a})) {
  176.                     int l = 0;
  177.                     j = sz(h) - 1;
  178.                     while (j - l > 1) {
  179.                         int mid = (l + j) / 2;
  180.                         if (lessByAngle(h[mid + 1] - h[mid], {b, -a}) && (h[mid + 1] - h[mid]) % point(b, -a) != 0)
  181.                             l = mid;
  182.                         else
  183.                             j = mid;
  184.                     }
  185.                 }
  186.             }
  187.         }
  188.         if (sign(a * h[i].x + b * h[i].y + c) * sign(a * h[j].x + b * h[j].y + c) <= 0)
  189.             ans.push_back(t);
  190.         ++t;
  191.     }
  192.     cout << sz(ans) << endl;
  193.     for (auto& i : ans)
  194.         cout << i << ' ';
  195.     cout << endl;
  196. }
  197.  
  198. signed main() {
  199.     ios::sync_with_stdio(false);
  200.     cin.tie(nullptr);
  201.  
  202.     int tt = 1;
  203.     //    cin >> tt;
  204.     while (tt--)
  205.         solve();
  206.  
  207.     return 0;
  208. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement