Submission #888165

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888165	2023-12-16T09:13:42 Z	ad_red	Tri (CEOI09_tri)	C++17	20 / 100	1287 ms	6728 KB

tri

#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() >= 2 && 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 in the angle
    // right_end - rightmost point in 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 = r;
    }
  
    {
      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 = l;
    }
  
    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 != sqrt_size - 1)) {
      if (in_triangle(a, Point{0LL, 0LL}, b, points[right_end])) {
        flag = true;
      }
      right_end--;
    }

    // assert(right_end % sqrt_size == 0);
    // assert(left_start % sqrt_size == 0);
  
    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 == (ll)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:196:102: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  196 |         if (mid + 1 == (ll)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	5 ms	348 KB	Output is correct
3	Incorrect	270 ms	2260 KB	Output isn't correct
4	Incorrect	658 ms	3744 KB	Output isn't correct
5	Incorrect	1287 ms	6728 KB	Output isn't correct
6	Incorrect	818 ms	5312 KB	Output isn't correct
7	Incorrect	1024 ms	6480 KB	Output isn't correct
8	Incorrect	466 ms	5504 KB	Output isn't correct
9	Incorrect	524 ms	6084 KB	Output isn't correct
10	Incorrect	574 ms	6332 KB	Output isn't correct