| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | maspy | 150 |
| 3 | Um_nik | 146 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | Dominater069 | 131 |
| 9 | Proof_by_QED | 130 |
| 9 | AmShZ | 130 |
|
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. |
|
+10
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. |
| Name |
|---|


