Submission #887756

#	Time	Username	Problem	Language	Result	Execution time	Memory
887756		ad_red	Tri (CEOI09_tri)	C++17	0 / 100	368 ms	5072 KiB

tri

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;
  
struct Point{
  int x, y;
};

int vp(Point a, Point b) {
  return a.x * b.y - a.y * b.x;
}

int 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
  
  int 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 int sqrt_size = 600;
  
int main() {
  int n, m;
  cin >> n >> m;
  
  for (int i = 0; i < n; i++) {
    int 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 (int i = 0; i < n; i++) {
    hulls[i / sqrt_size].push_back(points[i]);
  }
  
  
  for (int 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[(int)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 (int 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) == 1) swap(a, b);
  
    int left_start = n - 1, right_end = 0;
  
    // left_start - leftmost point that is in the angle
    // right_end - leftmost point after the angle
  
    int l = -1;
    int r = n - 1;
  
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (sgn(a, Point{0, 0}, points[mid]) >= 0) {
        l = mid;
      } else {
        r = mid;
      }
    }
  
    left_start = r;
  
    l = 0;
    r = n;
  
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if (sgn(b, Point{0, 0}, points[mid]) >= 0) {
        l = mid;
      } else {
        r = mid;
      }
    }
  
    right_end = r;
  
    if (l >= r) {
      cout << "N" << endl;
      continue;
    }
  
    bool flag = false;
  
    if (right_end - left_start <= sqrt_size) {
      for (int i = left_start; i < right_end; i++) {
        if (in_triangle(a, Point{0, 0}, 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{0, 0}, b, points[left_start])) {
        flag = true;
      }
      left_start++;
    }

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

Compilation message (stderr)

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

• Subtask 1: 0 / 100