# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
888166 | ad_red | Tri (CEOI09_tri) | C++17 | 1030 ms | 6580 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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].clear();
for (auto c : hull) {
hulls[i].push_back(c);
}
// 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 = 0, right_end = n - 1;
// left_start - leftmost point in the angle
// right_end - rightmost point in the angle
{
ll l = -1;
ll r = n - 1;
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;
right_end = l;
} else {
r = mid;
}
}
}
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |