#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) {if(a.m == b.m) return a.c > b.c; else return a.m > b.m; }); //BUG: Did not account for equal gradients
for(line curr: emb) {
while(sta.size() and (sta.back().second.m == curr.m or bye(sta.back(), curr))) {
sta.pop_back();
}
ld ccut = -1e18;
if(sta.size()) {
ccut = interx(curr, sta.back().second);
}
if(ccut <= 1e18) sta.push_back({ccut, curr});
}
// cerr << "Yep done\n";
}
bool query(ld x, ld maxy) {
auto lb = upper_bound(begin(sta), end(sta), x,
[](ld q, pair<ld, line> a) {
return q < a.first;
}
); //BUG: Upper bound was so much more weird compared to lower bound
//Otherwise code was good, trust your code.
assert(lb != begin(sta));
lb = prev(lb);
line now = lb->second;
ld lhs = (now.m * (ld)x + now.c);
return lhs <= (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;
// cerr << m << ' ' << b << '\n';
bool res = cht.query(m, b);
if(res) {
cout << "Y\n";
} else {
cout << "N\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
18 ms |
1568 KB |
Output is correct |
| 4 |
Correct |
38 ms |
4816 KB |
Output is correct |
| 5 |
Correct |
77 ms |
8588 KB |
Output is correct |
| 6 |
Incorrect |
49 ms |
6352 KB |
Output isn't correct |
| 7 |
Incorrect |
62 ms |
4804 KB |
Output isn't correct |
| 8 |
Incorrect |
71 ms |
5328 KB |
Output isn't correct |
| 9 |
Incorrect |
61 ms |
6612 KB |
Output isn't correct |
| 10 |
Incorrect |
65 ms |
5584 KB |
Output isn't correct |
