Comments
On MankiratAulakhCodejam round1B, 5 years ago
0

Isitpossible is rarely monotonic (A = 1 is maybe the only case where you can easily say that it is). This is most obvious when A and B aren't coprime (checking separate parities isn't enough) but generally it also isn't when A and B are coprime, and it's not hard to come up with examples where one can see this on paper.

Problem 1 can be attacked with duality. Suppose you have a line segment (x1,y1) to (x1,y2). Then the set of pairs (m,b) defining lines that pass through the segment are exactly the pairs satisfying:

$$$y1 \lt = mx1 + b \lt = y2$$$

which can be rewritten as:

$$$y1 - mx1 \lt = b \lt = y2 - mx1$$$

Now if we consider m and b as our variables, this defines 2 half planes that our pair (m,b) must live in. Take this over all the segments and the problem reduces to finding if intersection of a set of half planes is non-empty which is well known (e.g: https://codeforces.me/topic/62055/en1)

And actually the problems seem equivalent at least if you allow some of your vertical segments to be rays. But I think you can simulate rays by just taking large enough y coordinates.