#include <iostream>
#include <algorithm>
#include <vector>
#define fs first
#define se second
using namespace std;
typedef long long llong;
typedef pair<int, int> pii;
int cmp(pii a, pii b) {
llong L = (llong)a.se * b.fs;
llong R = (llong)a.fs * b.se;
if (L < R) return -1;
if (L > R) return 1;
return 0;
}
pii operator-(pii a, pii b) {
return pii(a.fs - b.fs, a.se - b.se);
}
int ccw(pii a, pii b) {
llong ret = (llong)a.fs * b.se - (llong)a.se * b.fs;
if (ret < 0) return -1;
if (ret > 0) return 1;
return 0;
}
int ccw(pii a, pii b, pii c) {
return ccw(b - a, c - b);
}
int n, q;
pii ps[100000];
vector<pii> low[1 << 18], upp[1 << 18];;
void get_convex_hull(int s, int e, vector<pii> &lo, vector<pii> &up) {
vector<pii> P;
for (int i = s; i <= e; ++i) {
P.push_back(ps[i]);
}
sort(P.begin(), P.end());
for (pii i : P) {
int sz;
while ((sz = lo.size()) > 1 && ccw(lo[sz - 2], lo[sz - 1], i) >= 0)
lo.pop_back();
while ((sz = up.size()) > 1 && ccw(up[sz - 2], up[sz - 1], i) <= 0)
up.pop_back();
lo.push_back(i);
up.push_back(i);
}
}
void init(int i, int s, int e) {
get_convex_hull(s, e, low[i], upp[i]);
if (s == e) return;
int m = (s + e) / 2;
init(i << 1, s, m);
init(i << 1 | 1, m + 1, e);
}
bool check_lo(vector<pii> &hull, pii lo, pii hi) {
int s = 0, e = hull.size() - 1;
if (ccw(lo, hi, hull[s]) > 0) return 1;
if (ccw(lo, hi, hull[e]) > 0) return 1;
pii p = hi - lo;
if (p < pii(0, 0)) p.fs = -p.fs, p.se = -p.se;
while (s < e) {
int m = (s + e) / 2;
if (ccw(p, hull[m + 1] - hull[m]) > 0) e = m;
else s = m + 1;
}
return ccw(lo, hi, hull[s]) > 0;
}
bool check_up(vector<pii> &hull, pii lo, pii hi) {
int s = 0, e = hull.size() - 1;
if (ccw(lo, hi, hull[s]) > 0) return 1;
if (ccw(lo, hi, hull[e]) > 0) return 1;
pii p = hi - lo;
if (p < pii(0, 0)) p.fs = -p.fs, p.se = -p.se;
while (s < e) {
int m = (s + e) / 2;
if (ccw(p, hull[m + 1] - hull[m]) < 0) e = m;
else s = m + 1;
}
return ccw(lo, hi, hull[s]) > 0;
}
bool query(int i, int s, int e, int x, int y, pii lo, pii hi) {
if (e < x || y < s) return 0;
if (x <= s && e <= y)
return check_lo(low[i], lo, hi) || check_up(upp[i], lo, hi);
int m = (s + e) / 2;
return query(i << 1, s, m, x, y, lo, hi) ||
query(i << 1 | 1, m + 1, e, x, y, lo, hi);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> ps[i].fs >> ps[i].se;
}
sort(ps, ps + n, [&](pii a, pii b) {
return cmp(a, b) < 0;
});
init(1, 0, n - 1);
while (q--) {
pii a, b;
cin >> a.fs >> a.se >> b.fs >> b.se;
if (cmp(a, b) > 0) swap(a, b);
int L = lower_bound(ps, ps + n, a, [&](pii a, pii b) {
return cmp(a, b) < 0;
}) - ps;
int R = lower_bound(ps, ps + n, b, [&](pii a, pii b) {
return cmp(a, b) < 0;
}) - ps - 1;
printf(query(1, 0, n - 1, L, R, a, b) ? "Y\n" : "N\n");
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
12792 KB |
Output isn't correct |
| 2 |
Incorrect |
17 ms |
12920 KB |
Output isn't correct |
| 3 |
Incorrect |
102 ms |
18556 KB |
Output isn't correct |
| 4 |
Incorrect |
184 ms |
25704 KB |
Output isn't correct |
| 5 |
Incorrect |
357 ms |
36428 KB |
Output isn't correct |
| 6 |
Incorrect |
395 ms |
27176 KB |
Output isn't correct |
| 7 |
Incorrect |
521 ms |
30160 KB |
Output isn't correct |
| 8 |
Incorrect |
410 ms |
28804 KB |
Output isn't correct |
| 9 |
Incorrect |
459 ms |
29988 KB |
Output isn't correct |
| 10 |
Incorrect |
522 ms |
31452 KB |
Output isn't correct |
