#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define int long long
#define EPS (ld)(1e-14)
#define vt vector
int K,M;
struct line {
ld m;
ld c;
line() {}
line(ld a, ld b) {
m = a;
c = b;
}
};
ld interx(line a, line b) {
ld res = (ld)(b.c - a.c) / (ld)(a.m - b.m);
return res;
}
struct {
vt<line> emb;
vt<pair<ld, line>> sta;
void push(line g) {
emb.push_back(g);
}
bool bye(pair<ld, line> g, line h) {
ld cut = g.first;
if(interx(g.second, h) <= cut) {
return true;
}
return false;
}
void solve() {
sort(begin(emb), end(emb), [](line a, line b) {return a.m > b.m; });
for(line curr: emb) {
while(sta.size() and bye(sta.back(), curr)) {
sta.pop_back();
}
ld ccut = 0;
if(sta.size()) {
ccut = interx(curr, sta.back().second);
}
sta.push_back({ccut, curr});
}
}
bool query(int x, int maxy) {
auto lb = lower_bound(begin(sta), end(sta), x,
[](pair<ld, line> a, int q) {
return a.first < (ld)q;
}
);
line now = lb->second;
return now.m * x + now.c <= (ld)maxy;
}
} cht;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> K >> M;
for(int i = 1; i <= K; i++) {
int xp, yp;
cin >> xp >> yp;
cht.push(line(-xp, yp));
}
cht.solve();
for(int g = 1; g <= M; g++) {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
ld m = (ld)(y2 - y1) / (ld)(x2 - x1);
ld b = -m * (ld)x1 + (ld)y1;
bool res = cht.query(m, b);
if(res) {
cout << "Y\n";
} else {
cout << "N\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
17 ms |
2428 KB |
Output isn't correct |
| 4 |
Incorrect |
28 ms |
4168 KB |
Output isn't correct |
| 5 |
Incorrect |
59 ms |
8820 KB |
Output isn't correct |
| 6 |
Incorrect |
45 ms |
7648 KB |
Output isn't correct |
| 7 |
Incorrect |
57 ms |
9348 KB |
Output isn't correct |
| 8 |
Incorrect |
48 ms |
7644 KB |
Output isn't correct |
| 9 |
Incorrect |
53 ms |
9408 KB |
Output isn't correct |
| 10 |
Incorrect |
60 ms |
9660 KB |
Output isn't correct |
