#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double ld;
typedef pair<int, int> pii;
#define fi first
#define se second
#define pb push_back
const int MAXN = 100010;
const int MX = 1 << 17;
const pii ori = pii(0, 0);
int N, M;
pii dot[MAXN];
pii tri[MAXN][2], p[MAXN];
int qs[MAXN];
vector<int> que[2 * MX];
bool ans[MAXN];
vector<int> ch[2 * MX];
lint cp(pii a, pii b) { return (lint)a.fi * b.se - (lint)a.se * b.fi; }
lint ccw(pii a, pii b, pii c) { return cp(a, b) + cp(b, c) + cp(c, a); }
bool cmp(const pii a, const pii b) { return ccw(ori, a, b) > 0; };
int lwb(pii &a) { return lower_bound(dot, dot + N, a, cmp) - dot; }
pii operator-(pii a, pii b) { return pii(a.fi - b.fi, a.se - b.se); }
void addquery(int idx, int l, int r, int x, int y, int z) {
if(x <= l && r <= y) que[idx].pb(z);
else if(l <= y && x <= r) {
int m = (l + r) / 2;
addquery(idx * 2, l, m, x, y, z);
addquery(idx * 2 + 1, m + 1, r, x, y, z);
}
}
void f(int idx, int l, int r) {
/*
printf("f(idx = %d, l = %d, r = %d)\n", idx, l, r);
printf("que : ");
for(auto a : que[idx]) printf("%d ", a);
puts("");
*/
if(l == r) ch[idx].push_back(l);
else {
int m = (l + r) / 2;
f(idx * 2, l, m);
f(idx * 2 + 1, m + 1, r);
ch[idx].push_back(ch[idx * 2][0]);
int t = 0;
for(auto a : ch[idx * 2]) if(a != ch[idx * 2].back()) {
for(; t + 1 < ch[idx * 2 + 1].size(); t++)
if(ccw(dot[ch[idx * 2 + 1][t]], dot[ch[idx * 2][0]], dot[ch[idx * 2 + 1][t + 1]]) >= 0)
break;
if(ccw(dot[a], dot[a], dot[ch[idx * 2 + 1][t]]) > 0)
ch[idx].push_back(a);
else break;
}
for(int i = t; i < ch[idx * 2 + 1].size(); i++)
ch[idx].push_back(ch[idx * 2 + 1][i]);
ch[idx * 2].clear();
ch[idx * 2 + 1].clear();
}
int t = 0;
for(auto a : que[idx]) {
while(t + 1 < ch[idx].size() && ccw(tri[a][0], dot[ch[idx][t]], tri[a][1]) > ccw(tri[a][0], dot[ch[idx][t + 1]], tri[a][1]))
t++;
ans[a] |= ccw(dot[ch[idx][t]], tri[a][0], tri[a][1]) > 0;
}
/*
printf("ch[%d] : ", idx);
for(auto a : ch[idx]) printf("%d ", a);
puts("");
printf("end f(%d)\n", idx);
*/
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
for(int i = 0; i < N; i++) cin >> dot[i].fi >> dot[i].se;
for(int i = 0; i < M; i++) for(int j = 0; j < 2; j++) cin >> tri[i][j].fi >> tri[i][j].se;
sort(dot, dot + N, cmp);
for(int i = 0; i < M; i++) {
qs[i] = i;
if(!cmp(tri[i][0], tri[i][1])) swap(tri[i][0], tri[i][1]);
p[i] = tri[i][1] - tri[i][0];
}
sort(qs, qs + M, [&](const int a, const int b) {
if(p[a].se < 0 && p[b].se >= 0) return false;
if(p[a].se >= 0 && p[b].se < 0) return true;
return cmp(p[a], p[b]);
});
for(int i = 0; i < M; i++)
addquery(1, 0, N - 1, lwb(tri[qs[i]][0]), lwb(tri[qs[i]][1]) - 1, qs[i]);
f(1, 0, N - 1);
for(int i = 0; i < M; i++) cout << (ans[i] ? "Y" : "N") << "\n";
return 0;
}
Compilation message
tri.cpp: In function 'void f(int, int, int)':
tri.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; t + 1 < ch[idx * 2 + 1].size(); t++)
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = t; i < ch[idx * 2 + 1].size(); i++)
~~^~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(t + 1 < ch[idx].size() && ccw(tri[a][0], dot[ch[idx][t]], tri[a][1]) > ccw(tri[a][0], dot[ch[idx][t + 1]], tri[a][1]))
~~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
12792 KB |
Output isn't correct |
| 2 |
Incorrect |
15 ms |
12792 KB |
Output isn't correct |
| 3 |
Incorrect |
55 ms |
17020 KB |
Output isn't correct |
| 4 |
Incorrect |
85 ms |
20088 KB |
Output isn't correct |
| 5 |
Incorrect |
161 ms |
27476 KB |
Output isn't correct |
| 6 |
Incorrect |
318 ms |
33308 KB |
Output isn't correct |
| 7 |
Incorrect |
408 ms |
38904 KB |
Output isn't correct |
| 8 |
Incorrect |
314 ms |
31812 KB |
Output isn't correct |
| 9 |
Incorrect |
394 ms |
34216 KB |
Output isn't correct |
| 10 |
Incorrect |
367 ms |
36600 KB |
Output isn't correct |
