#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;
};
void pv(vector<Point> s) {
for (auto c : s) {
cout << "{" << c.x << ", " << c.y << "} ";
}
cout << endl;
}
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 = 600;
int main() {
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(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);
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 = -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;
}
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;
}
}
if (flag) {
cout << "Y" << endl;
continue;
}
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], 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
tri.cpp: In function 'int main()':
tri.cpp:211: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]
211 | 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:211:94: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
211 | 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:218:67: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
218 | for (int j = (l - 3 + hulls[i].size()) % hulls[i].size(); j <= (r + 3 + hulls[i].size()) % hulls[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
130 ms |
2352 KB |
Output isn't correct |
| 4 |
Incorrect |
325 ms |
3728 KB |
Output isn't correct |
| 5 |
Incorrect |
955 ms |
6856 KB |
Output isn't correct |
| 6 |
Incorrect |
653 ms |
5864 KB |
Output isn't correct |
| 7 |
Incorrect |
814 ms |
6800 KB |
Output isn't correct |
| 8 |
Incorrect |
365 ms |
5560 KB |
Output isn't correct |
| 9 |
Incorrect |
401 ms |
6152 KB |
Output isn't correct |
| 10 |
Incorrect |
481 ms |
7260 KB |
Output isn't correct |
