oj.uz

Submission #887849

# Submission time Handle Problem Language Result Execution time Memory
887849 2023-12-15T10:04:18 Z ad_red Tri (CEOI09_tri) C++17
20 / 100
 1104 ms 6816 KB 
#include <bits/stdc++.h>
#define endl "\n"
  
using namespace std;
using ll = long long;

  
struct Point{
  ll x, y;
};
  
ll vp(Point a, Point b) {
  return a.x * b.y - a.y * b.x;
}
  
ll sgn(Point a, Point b, Point c) {
  // -1 if the order is A-B-C from left to right if B is the bottom point
  // 1 or 0 otherwise
  
  ll q = vp(Point{a.x - b.x, a.y - b.y}, Point{c.x - b.x, c.y - b.y});
  return (q / abs(q));
}
  
bool operator<(Point a, Point b) {
  return sgn(a, Point{0LL, 0LL}, b) == -1;
}
  
bool in_triangle(Point a, Point b, Point c, Point p) {
  // assuming A-B-C
  
  return (sgn(a, b, p) == -1 && sgn(c, b, p) == 1 && sgn(p, c, a) == -1);
}
  
bool cmp_hull(Point a, Point b) {
  if (a.x == b.x) return a.y < b.y;
  return a.x < b.x;
}
  
/*
  Plan:
  0. Sort all points by angle
  1. Construct sqrt(n) convex hulls for all point sets
  2. For each triangle, consider all sqrt(n) ranges of points already present
  3. Check all points that are outside of the hulls manually
  3.5 On both sides
  4. For each complete range with a hull do a binary search on that hull:
  5. Start with the leftmost (by the angle) point, end with the point anticlockwise on the convex hull
  6. Check if the mid is in the triangle, if it is, then break. If we are moving further from the triangle by choosing a point to the right of the current one (cur_mid), then r = mid, else l = mid.
  
  Claim: the total thing takes no more than 200 lines.
*/
  
vector<Point> points;
const ll sqrt_size = 1200;

signed main() {
  ll n, m;
  cin >> n >> m;
  
  for (ll i = 0; i < n; i++) {
    ll x, y;
    cin >> x >> y;
  
    points.push_back(Point{x, y});
  }
  
  sort(points.begin(), points.end()); // the comparator is there
  
  vector<vector<Point>> hulls(n);
  
  for (ll i = 0; i < n; i++) {
    hulls[i / sqrt_size].push_back(points[i]);
  }
  
  
  for (ll i = 0; i < n; i++) {
    if (hulls[i].empty()) continue;
    
    vector<Point> hull;
  
    sort(hulls[i].begin(), hulls[i].end(), cmp_hull);
  
    for (auto p : hulls[i]) {
      while (hull.size() > 1 && sgn(p, hull[(ll)hull.size() - 2], hull.back()) == -1) {
        hull.pop_back();
      }
      hull.push_back(p);
    }
  
    hulls[i] = hull;
    // top convex hull only!
  }
  
  // end of hull processing
  
  for (ll trn = 0; trn < m; trn++) {
    // current triangle
  
    Point a, b;
    cin >> a.x >> a.y >> b.x >> b.y;
  
    if (sgn(a, Point{0LL, 0LL}, b) >= 0) swap(a, b);
  
    ll left_start = n - 1, right_end = 0;
  
    // left_start - leftmost point that is in the angle
    // right_end - leftmost point after the angle
    {
      ll l = 0;
      ll r = n;
    
      while (r - l > 1) {
        ll mid = (l + r) / 2;
        if (sgn(a, Point{0LL, 0LL}, points[mid]) >= 0) {
          l = mid;
        } else {
          r = mid;
        }
      }
    
      left_start = l;
    }
  
    {
      ll l = 0;
      ll r = n;
    
      while (r - l > 1) {
        ll mid = (l + r) / 2;
        if (sgn(b, Point{0LL, 0LL}, points[mid]) >= 0) {
          l = mid;
        } else {
          r = mid;
        }
      }
    
      right_end = r;
    }
  
    if (left_start >= right_end) {
      cout << "N" << endl;
      continue;
    }
  
    bool flag = false;
  
    if (right_end - left_start <= sqrt_size) {
      for (ll i = left_start; i < right_end; i++) {
        if (in_triangle(a, Point{0LL, 0LL}, b, points[i])) {
          flag = true;
          break;
        }
      }
  
      if (flag) {
        cout << "Y" << endl;
      } else {
        cout << "N" << endl;
      }
  
      continue;
    }
  
    flag = false;
  
    while (left_start % sqrt_size != 0) {
      if (in_triangle(a, Point{0LL, 0LL}, b, points[left_start])) {
        flag = true;
      }
      left_start++;
    }
  
    while (right_end > left_start && right_end % sqrt_size != 0) {
      right_end--;
      if (in_triangle(a, Point{0LL, 0LL}, b, points[right_end])) {
        flag = true;
      }
    }

    if (left_start == right_end) {
      if (flag) {
        cout << "Y" << endl;
      } else {
        cout << "N" << endl;
      }
      continue;
    }

    // assert(right_end % sqrt_size == 0);
    assert(left_start % sqrt_size == 0);
  
    flag = false;
  
    for (ll i = left_start / sqrt_size; i < right_end / sqrt_size; i++) {
      // convex hull processing
  
      ll l = 0;
      ll r = (ll)hulls[i].size();
  
      while (r - l > 1) {
        ll mid = (r + l) / 2;
  
        if (in_triangle(a, Point{0LL, 0LL}, b, hulls[i][mid])) {
          flag = true;
          break;
        }
  
        if (mid + 1 == hulls[i].size() || !in_triangle(a, Point{0LL, 0LL}, b, hulls[i][mid + 1]) && sgn(hulls[i][mid + 1], a, hulls[i][mid]) == -1) {
          r = mid;
        } else {
          l = mid;
        }
      }
  
      if (flag) break;
    }
  
    if (flag) {
      cout << "Y" << endl;
    } else {
      cout << "N" << endl;
    }
  }
  
  return 0;
}

Compilation message

tri.cpp: In function 'int main()':
tri.cpp:208:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |         if (mid + 1 == hulls[i].size() || !in_triangle(a, Point{0LL, 0LL}, b, hulls[i][mid + 1]) && sgn(hulls[i][mid + 1], a, hulls[i][mid]) == -1) {
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~
tri.cpp:208:98: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  208 |         if (mid + 1 == hulls[i].size() || !in_triangle(a, Point{0LL, 0LL}, b, hulls[i][mid + 1]) && sgn(hulls[i][mid + 1], a, hulls[i][mid]) == -1) {
      |                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Incorrect 98 ms 2276 KB Output isn't correct
4 Incorrect 387 ms 3784 KB Output isn't correct
5 Incorrect 755 ms 6588 KB Output isn't correct
6 Incorrect 902 ms 5568 KB Output isn't correct
7 Incorrect 1104 ms 6788 KB Output isn't correct
8 Incorrect 452 ms 5128 KB Output isn't correct
9 Incorrect 517 ms 6160 KB Output isn't correct
10 Incorrect 584 ms 6816 KB Output isn't correct