#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define X first
#define Y second
#define sz(V) ((int)V.size())
struct query { int id; pll A, B; };
int CCW(pll A, pll B, pll C) {
long long tmp = A.X*B.Y + B.X*C.Y + C.X*A.Y - A.Y*B.X - B.Y*C.X - C.Y*A.X;
if(tmp < 0LL) return -1;
if(tmp == 0LL) return 0;
if(tmp > 0LL) return +1;
}
bool operator <(pll A, pll B) { return CCW({0, 0}, A, B) == 1; }
bool operator <=(pll A, pll B) { return CCW({0, 0}, A, B) >= 0; }
pll add(pll A, pll B, pll C) {
return {A.X + C.X - B.X, A.Y + C.Y - B.Y};
}
bool chk(vector<pll> &H, pll A, pll B) {
if(B < A) swap(A, B);
bool f = 0;
int l = 0, r = sz(H) - 1;
while(l <= r) {
int m = l+r >> 1;
if(CCW(A, B, H[m]) == 1) f = 1;
if(m+1 == sz(H) || CCW(A, B, add(B, H[m], H[m+1])) == -1) r = m-1;
else l = m+1;
}
return f;
}
pll P[100009];
bool ans[100009];
vector<query> S[300009];
void go(int idx, int s, int e, pll A, pll B, int id) {
if(e < s || B <= P[s] || P[e] <= A) return;
int m = s+e >> 1;
if(A < P[m] && P[m] < B) {
S[idx].push_back({id, A, B});
return;
}
go(idx*2, s, m-1, A, B, id);
go(idx*2+1, m+1, e, A, B, id);
}
void dnc(int idx, int s, int e) {
if(e < s) return;
int m = s+e >> 1;
{
sort(S[idx].begin(), S[idx].end(), [&](query PP, query QQ) { return PP.B < QQ.B; });
vector<pll> H;
int i = m;
for(auto& it: S[idx]) {
while(i <= e && P[i] < it.B) {
while(sz(H) >= 2 && CCW(H[sz(H) - 2], H[sz(H) - 1], P[i]) >= 0) H.pop_back();
H.push_back(P[i]);
++i;
}
ans[it.id] |= chk(H, it.A, it.B);
}
}
{
sort(S[idx].begin(), S[idx].end(), [&](query PP, query QQ) { return QQ.A < PP.A; });
vector<pll> H;
int i = m;
for(auto& it: S[idx]) {
while(i >= s && it.A < P[i]) {
while(sz(H) >= 2 && CCW(H[sz(H) - 2], H[sz(H) - 1], P[i]) <= 0) H.pop_back();
H.push_back(P[i]);
--i;
}
ans[it.id] |= chk(H, it.A, it.B);
}
}
dnc(idx*2, s, m-1);
dnc(idx*2+1, m+1, e);
}
int main() {
int K, M; scanf("%d%d",&K,&M);
for(int i=1; i<=K; i++) scanf("%lld%lld", &P[i].X, &P[i].Y);
sort(P+1, P+K+1, [&](pll PP, pll QQ) { return PP < QQ; });
for(int i=1; i<=M; i++) {
pll A, B; scanf("%lld%lld%lld%lld", &A.X, &A.Y, &B.X, &B.Y);
if(B < A) swap(A, B);
go(1, 1, K, A, B, i);
}
dnc(1, 1, K);
for(int i=1; i<=M; i++) puts(ans[i] ? "Y" : "N");
return 0;
}
Compilation message
tri.cpp: In function 'bool chk(std::vector<std::pair<long long int, long long int> >&, pll, pll)':
tri.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l+r >> 1;
~^~
tri.cpp: In function 'void go(int, int, int, pll, pll, int)':
tri.cpp:44:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
tri.cpp: In function 'void dnc(int, int, int)':
tri.cpp:55:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
tri.cpp: In function 'int CCW(pll, pll, pll)':
tri.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
tri.cpp: In function 'int main()':
tri.cpp:87:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int K, M; scanf("%d%d",&K,&M);
~~~~~^~~~~~~~~~~~~~
tri.cpp:88:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=K; i++) scanf("%lld%lld", &P[i].X, &P[i].Y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tri.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
pll A, B; scanf("%lld%lld%lld%lld", &A.X, &A.Y, &B.X, &B.Y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
7544 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7544 KB |
Output is correct |
| 3 |
Correct |
41 ms |
9320 KB |
Output is correct |
| 4 |
Correct |
78 ms |
10916 KB |
Output is correct |
| 5 |
Correct |
156 ms |
14180 KB |
Output is correct |
| 6 |
Correct |
130 ms |
12452 KB |
Output is correct |
| 7 |
Correct |
165 ms |
14284 KB |
Output is correct |
| 8 |
Correct |
158 ms |
12812 KB |
Output is correct |
| 9 |
Correct |
178 ms |
13424 KB |
Output is correct |
| 10 |
Correct |
202 ms |
14100 KB |
Output is correct |
