Anyone can help solve problem problem GOODG? I can't figure out how to apply Convex Hull DP since the lines won't be added in sorted order.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Anyone can help solve problem problem GOODG? I can't figure out how to apply Convex Hull DP since the lines won't be added in sorted order.
Name |
---|
Anyone?
Read the paragraph "Fully dynamic variant" of this article
While you could use convex hull dp to solve this problem, it is unnecessary. Since time is always increasing and you always add new lines to the top, you can just maintain a stack of active lines, deleting them when they become irrelevant.
this problem can be solved using Sweep line algorithm by Bentley-Ottmann. Refer this link: 'http://geomalgorithms.com/a09-_intersect-3.html' for this algorithm. in worst case, no. of intersections can be O(N). when a upper line cross the lower line, then make this upper line inactive. So, when a intersection happens, one line is getting delete. so, max of O(N) intersections can happen in worst.