Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement