#include<bits/stdc++.h>
using namespace std;
#define cerr while(0) cerr
#define ld long double
#define int long long
#define EPS (ld)(2e-9)
#define x first
#define y second
#define vt vector
const int maxn = 1e5+5;
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 cht {
bool PREPPED = 0;
vt<line> emb;
vt<pair<ld, line>> sta;
void push(line g) {
if(PREPPED) {
cerr << "Tried inserting on query-only mode!\n";
assert(1 == 2);
}
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) {
if(not PREPPED) { //BUG: Solve needs to always be before stack condition
cerr << "Query-only mode activated\n";
solve();
PREPPED = true;
}
cerr << "I can reach this\n";
if(sta.empty()) { //BUG: should've checked empty case
return false;
}
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;
}
};
struct rational {
int p, q;
rational() {}
rational(int a, int b) {
p = a, q = b;
}
friend bool operator==(rational a, rational x) {
if(x.q == a.q and a.q == 0) {
return true;
} else if((x.q == 0 and a.q != 0) or (x.q != 0 and a.q == 0)) {
return false;
}
return a.p * x.q == a.q * x.p;
}
friend bool operator<(rational a, rational x) {
assert(a.p >= 0 and a.q >= 0);
assert(x.p >= 0 and x.q >= 0);
if(a.q == 0) return false;
if(x.q == 0) return true;
return a.p * x.q < a.q * x.p;
}
};
struct seg {
int tl, tr;
seg *lc, *rc;
cht db;
bool has_child = 0;
seg() {}
seg(int a, int b) {
tl = a, tr = b;
}
void split() {
if(has_child or tl == tr) return;
has_child = true;
int tm = (tl+tr)/2;
lc = new seg(tl, tm);
rc = new seg(tm+1, tr);
}
bool query(int l, int r, ld m, ld b) {
if(tl == l and tr == r) { //BUG: l == r instead of tl == l and tr == r
return db.query(m, b);
}
assert(tl <= l and r <= tr);
int tm = (tl+tr)/2;
split();
bool res = 0;
if(l <= tm) {
res = res or lc->query(l, min(tm,r), m, b); //BUG: should be l, min(tm,r)
}
if(tm < r) {
res = res or rc->query(max(tm+1,l), r, m, b); //BUG: should be max(tm+1,l), r
}
return res;
}
void upd(int pseu, line u) {
if(tl == tr) {
db.push(u);
return;
}
int tm = (tl+tr)/2;
split();
db.push(u);
if(pseu <= tm) {
lc->upd(pseu, u);
} else {
rc->upd(pseu, u);
}
}
};
pair<ld, ld> qs[maxn];
pair<int, int> points[maxn];
bool ans[maxn];
int linp[maxn]; //pseudo gradient of a point
pair<int, int> qran[maxn]; //pseudo gradients of query ranges
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> K >> M;
vector<pair<rational, int>> mps; //object id
for(int i = 1; i <= K; i++) {
int xp, yp;
cin >> xp >> yp;
// cerr << (rational(1,1) == rational(2,2)) << '\n';
// cht.push(line(-xp, yp));
mps.push_back({rational(yp, xp), i});
points[i] = {xp, yp};
}
// cht.solve();
for(int g = 1; g <= M; g++) {
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
rational lo (y1, x1), hi (y2, x2);
if(hi < lo) swap(lo, hi);
ld m = ((ld)(y2 - y1)) / ((ld)(x2 - x1));
ld b = -m * (ld)x1 + (ld)y1;
mps.push_back({lo, g+K});
mps.push_back({hi, g+K});
// cerr << m << ' ' << b << '\n';
// bool res = cht.query(m, b);
qs[g] = {m, b};
}
int ptr = 0;
int roll = 1;
sort(begin(mps), end(mps), [](pair<rational, int> a, pair<rational,int> b) { return a.x < b.x; });
while(ptr < mps.size()) {
vector<int> these;
rational cur = mps[ptr].x;
while(ptr < mps.size() and mps[ptr].x == cur) {
these.push_back(mps[ptr].y);
ptr++;
}
for(int it : these) {
if(it <= K) {
linp[it] = roll;
} else {
//AVOIDED BUG: it -= K;
it -= K;
if(qran[it].x == 0) {
qran[it].x = roll;
} else {
qran[it].y = roll;
}
}
}
roll++;
}
seg* root = new seg(1, roll-1);
for(int i = 1; i <= K; i++) {
int xp = points[i].x, yp = points[i].y;
//REMEMBER: (-xp, yp) for line
root->upd(linp[i], line(-xp, yp));
}
for(int g = 1; g <= M; g++) {
ans[g] = root->query(qran[g].x, qran[g].y, qs[g].x, qs[g].y);
}
for(int i = 1; i <= M; i++) {
if(ans[i]) {
cout << "Y\n";
} else {
cout << "N\n";
}
}
}
Compilation message
tri.cpp: In function 'int main()':
tri.cpp:369:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<rational, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
369 | while(ptr < mps.size()) {
| ~~~~^~~~~~~~~~~~
tri.cpp:375:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<rational, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
375 | while(ptr < mps.size() and mps[ptr].x == cur) {
| ~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
57 ms |
31944 KB |
Output is correct |
| 4 |
Correct |
105 ms |
59636 KB |
Output is correct |
| 5 |
Runtime error |
136 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
119 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
133 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
116 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
155 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
139 ms |
65536 KB |
Execution killed with signal 9 |
