#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using ll = long long;
template<class T> bool ckmin(T&a, const T& b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T&a, const T& b) { return a < b ? a = b, true : false; }
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;
const int N = 1e5 + 5;
struct Point {
ll x;
ll y;
bool operator < (Point other) {
return x * other.y > y * other.x;
}
};
Point p[N];
int cmp(Point a, Point b) {
ll val = a.x * b.y - a.y * b.x;
if (val == 0) return 0;
if (val < 0) return 1;
if (val > -1) return -1;
}
ll area(Point a, Point b, Point c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
struct SegTree {
int n;
vector<vi> segt;
bool ans;
void convex_hull(vector<int> &hull, int l, int r) {
for (int i = l; i <= r; ++i) {
while (hull.size() >= 2 && area(p[hull[hull.size() - 1]], p[hull[hull.size() - 2]], p[i]) >= 0) hull.pop_back();
hull.push_back(i);
}
}
void build(int v, int tl, int tr) {
convex_hull(segt[v], tl, tr);
if (tl == tr) return;
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
}
SegTree(int nn) {
n = nn;
segt.resize(4 * n + 1);
build(1, 1, n);
}
bool solve(vector<int> &hull, Point a, Point b) {
int l = 0, r = hull.size() - 1;
while (l < r) {
int m = (l + r) / 2;
ll res1 = area(a, b, p[hull[m]]);
ll res2 = area(a, b, p[hull[m + 1]]);
if (res1 > res2) {
r = m - 1;
} else {
l = m + 1;
}
}
return area(a, b, p[hull[l]]) > 0;
}
void query(int v, int tl, int tr, Point a, Point b) {
if (ans == 1) return;
if (cmp(b, p[segt[v][0]]) < 0) return;
if (cmp(a, p[segt[v].back()]) > 0) return;
if (cmp(a, p[segt[v][0]]) <= 0 && cmp(p[segt[v].back()], b) <= 0) {
ans |= solve(segt[v], a, b);
return;
}
if (tl == tr) return;
int tm = (tl + tr) / 2;
query(2 * v, tl, tm, a, b);
query(2 * v + 1, tm + 1, tr, a, b);
}
bool get(Point a, Point b) {
ans = 0;
query(1, 1, n, a, b);
return ans;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
sort(p + 1, p + n + 1);
SegTree t(n);
while (m--) {
Point a, b;
cin >> a.x >> a.y >> b.x >> b.y;
if (cmp(a, b) > 0) swap(a, b);
cout << (t.get(a, b) ? "Y" : "N") << "\n";
}
}
Compilation message
tri.cpp: In function 'int cmp(Point, Point)':
tri.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
38 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 3 |
Incorrect |
22 ms |
6704 KB |
Output isn't correct |
| 4 |
Incorrect |
39 ms |
11356 KB |
Output isn't correct |
| 5 |
Incorrect |
84 ms |
22312 KB |
Output isn't correct |
| 6 |
Incorrect |
130 ms |
18600 KB |
Output isn't correct |
| 7 |
Incorrect |
169 ms |
23636 KB |
Output isn't correct |
| 8 |
Incorrect |
126 ms |
19028 KB |
Output isn't correct |
| 9 |
Incorrect |
144 ms |
21332 KB |
Output isn't correct |
| 10 |
Incorrect |
184 ms |
23632 KB |
Output isn't correct |
