oj.uz

Submission #887656

# Submission time Handle Problem Language Result Execution time Memory
887656 2023-12-15T00:37:04 Z ad_red Tri (CEOI09_tri) C++17
0 / 100
 33 ms 11220 KB 
#include <bits/stdc++.h>
#define endl "\n"

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;
using ld = long double;

ll inf = 1e9;

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 = 500;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  ll n, m;
  cin >> n >> m;

  for (int 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 (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(hull[(int)hull.size() - 2], hull.back(), p) == -1) {
        hull.pop_back();
      }
      hull.push_back(p);
    }

    hulls[i] = hull;
  }

  // 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);

    ll left_start, right_end;

    // left_start - leftmost point that is in the angle
    // right_end - leftmost point after the angle

    ll l = -1;
    ll r = n - 1;

    while (r - l > 1) {
      ll 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) {
      ll 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;
        break;
      }
      left_start++;
    }

    assert(left_start % sqrt_size == 0);

    while (right_end > left_start && right_end % sqrt_size > 0) {
      right_end--;
      if (in_triangle(a, Point{0, 0}, b, points[right_end])) {
        flag = true;
        break;
      }
    }

    assert(right_end > left_start && right_end % sqrt_size == 0);

    if (flag) {
      cout << "Y" << endl;
      continue;
    }

    return 0;

    flag = false;

    for (int i = left_start / sqrt_size; i < right_end / sqrt_size; i++) {
      // convex hull processing

      ll l = 0;
      ll r = (int)hulls[i].size();

      while (r - l > 1) {
        ll 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], hulls[i][mid], a) == 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

tri.cpp: In function 'int main()':
tri.cpp:212: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]
  212 |         if (mid + 1 == hulls[i].size() || !in_triangle(a, Point{0, 0}, b, hulls[i][mid + 1]) && sgn(hulls[i][mid + 1], hulls[i][mid], a) == 1) {
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~
tri.cpp:212:94: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  212 |         if (mid + 1 == hulls[i].size() || !in_triangle(a, Point{0, 0}, b, hulls[i][mid + 1]) && sgn(hulls[i][mid + 1], hulls[i][mid], a) == 1) {
      |                                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:219:67: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
  219 |       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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 10 ms 2596 KB Output isn't correct
4 Incorrect 16 ms 4312 KB Output isn't correct
5 Incorrect 33 ms 8008 KB Output isn't correct
6 Incorrect 21 ms 6344 KB Output isn't correct
7 Incorrect 25 ms 7880 KB Output isn't correct
8 Runtime error 29 ms 11220 KB Execution killed with signal 6
9 Incorrect 29 ms 7104 KB Output isn't correct
10 Incorrect 31 ms 7888 KB Output isn't correct