I got stuck at this problem while trying to learn sweep line technique. I've read the editorial for that problem and got seriously confused at the "y coordinate for a segment" part. Like ... how can we compare the y coordinate when a segment consist of two points ? (Apparently I think it has something to do with sorting points by increasing x coordinate, but can't figure out why ...). Also why do we only check for intersection with the "above" segment in the active set when we first meet the beginning of a segment, but check for both the "above" and "below" when we meet a segment's end ? Please explain all of my question in details if possible.
P/s : Remember that I have 2 questions ...
Edit: There's no respond ... At this point let me ask something straight, and possibly easier : Do you know any red or generally high ranked people that are willing to answer question from a noob like me ? I'm determined to get good at CP, but literally have no mentor or teacher that can go with me a long way. So I asked a friend long ago if he know a good community where people are willing to help me improve. He answered "Codeforces" and ... here I'm am, 3 years later, finally ready to change from a super lazy guy, ADHD and stuff ... to a better version of my self. I went to CF and all the blog I've posted, every characters I've written on CF is just about CP. Sometime I would receive help, but mostly, 80% of the time, it's just downvotes. I know a beginner like me will ask questions that some of you deem stupid, lame, etc... but I know I need to make mistakes to improve. Now I've set for myself a very difficult, rough goal, and time is against me (if I say what the goal is, I know some people will respond with even more negative feedback, but I'll give away a hint : I'm 17 by now). So I changed to a polyphasic sleep schedule recently, sleep for only 3-4 hours a day (yes that's possible), coding for 14-17h, The rest was spend on eating, taking bath, exercise, chores. The unusual time schedule give me more time, but in turn, I have to abandon CF ranked contest, as it always get in the way of one of my sleep phase. But as I study more, there's one clear disadvantage : I have no one to ask. Internet is a rich source of knowledge, but I can't just "figure it out" for every problem I met. I tried : go to CF -> ask a question -> get downvotes -> try even more to "figure it out" -> solve it, but cost too much time. Time is a luxury that I don't have. I know this blog will just earn me even more downvotes, but I don't really mind it. Please, if you know some one who have the patience and ability, along with kindness to answer some of my question, inform me of that person, I promise I will choose the question wisely (Generally I have a about 2 questions a day that are just beyond my ability because of my rapid pace of learning, failing, and trying (well 16h on average a day is a lot of time, I just have to do something with it) but even one answered question a week is already a bless. Most of my question posted on CF have no answer). I will just stay a grey (I've no other choice), but will try to be a student who work both hard and smart, if I ever have a teacher in CP.
Ah ... It's coming ... the downvotes. Can I just ask if I've offended somebody while trying to ask for help ? I'm little interested in the reason ^_^
Firstly, if your sole objective is to learn, stop caring about downvotes and your contribution. You can't control publics.
Secondly, when I try to read this blog, it just sucks me out of all desire to help you. Like, you could at least put the compact version of the problem statement, so that we won't have to click the link and decode the statement ourselves. No linebreaks between paragraphs either.
Helping someone on codeforces comment section requires quite a bit of effort, including understanding what you're not getting. If you want others to help regardless, you need to at least put some fraction of that effort into writing a blog which could help us ease that burden.
For the downvote part :
Add spaces to your text, to make it clearer.
When you ask for help, you thank people for any help, even if it's not helpful, It's the recognition that people took time for you and that you are grateful for it, even if you can't use their answer. Instead, you remind them to give you the whole help you need (that's related to your "plese remember i have 2 question...").
Using the magic legendary grand master rank to ask a newbie question probably also lead to more downvotes.
For the help that you ask : good news ! I believe that you don't need it to get better at CP !
You are working on a hurdle problem so I will keep the analogy. Solving a CP problem is getting throught a numbers of hurdles. Sometimes (mostly in high level problems), there are lots of hurdles and it takes time to go throught all of them. Most of the time, it's the height of the hurdle that matter.
If the hurdle is higher than what we can jump, we fail to solve the problem. If we fail by a short height, then we read the editorial and understand it instantly. If the margin is a bit larger, it takes time to understand the editorial. As the margin grow larger, it becomes more and more difficult to understand the editorial and at some point, we don't understand the editorial anymore. This is NORMAL and EXPECTED.
Back to more a practical point of vew : what can you do with your problem ? Simple answer : keep track of a list of problems that you currently can't solve and get back to it every month !
It's long enough so that you probably won't remember exactly the editorial you read the previous time, but short enough so that you didn't forgot everything about the problem. It's also pretty cool and motivating to see the improvement month after month.
Quite often you won't be able to solve the problem even after a month but you will understand the editorial faster, until at some point, you will either know the problem by heart and it will stick in your memory, or you will be able to solve it because you now know how to jump higher !
I hope, my answer, which is not what you wanted, still helped you !
Um thank you for your suggestion. I did in fact failed to thank some people, mainly because I only post questions late in the day, when I've already think for hours. So if I post it at 3.am, I just can fight the urge to sleep right after I see an answer and think it through. Some time I just sleep on my table till morning, But again, thank you, I'll fix that.
EDIT: Oh and I see you notice me changing to a LGM. That was intentional, too. I post this a while ago, with no one even care to read it. Obviously, you can see right ? people don't read a post by a grey. So I thought "What if I can scam people, get more attention to my post by making my name colorful ?". Remember that my objective was to have enough people to read it, so some of them will try to help me. I don't really mind being downvoted, as long as I can get help, learn something new, and improve. But hey, the trick worked !!!
One more thing I'd like to add to what he's said, you truly don't need a teacher. But, you need classmates, combative ones who won't cut you any slack, nemeses etc. People don't decline in intelligence as they grow older, they stopped feeling "pushed".
Please DO NOT do CP for 17 hours, the brain will end up "overfitting". If you don't believe me, google it. Speed/Attention is the fuel for problem solving. Some use a blanket term like "confidence", "form" etc. You need to be in form. From there, you can try to reach your best form.
You're still young, go outside everyday (at least out of your room), turn on the TV, watch CNN, see movies, try to beat a "commoner" at a "stupid" beach game, DO AN OUTDOOR SPORT. Go out with friends, family. Reset. These physical activities will not waste your time if you have fun doing them (in your free time), they will maintain your form, even improve your form if you're doing an outdoor competitive sport like soccer with friends. Solving problems is 50%, this is the other 50% you need to improve.
This new year magic thing really got me and was confused af...
Don't get upset. The problem is difficult and underrated. IMO it is equivalent to div2D on CF or so, because it's tricky to come up with. Also, i daresay editorial is shitty. Most of them are. The code is really hard to read.
So, for your first question. Imagine you have not a segment, but a line. Then, in order to get "the y coordinate of segment s when evaluated at x", you just need to substitude x with your current x0 in this equation y = k*x + b. The code does some sort of that in an exceptionally obfuscating way.
For your second question — you probably got confused. The solution checks for intersection of two neighbour segments when a segment is deleted (when you reached its end) and checks for intersection of current segment with upper one and lower one if it is about to be added to "active" pool of segments.
I don't think you completely understand what is going on in code and how the checks are performed, so feel free to ask me in PM.
P.S. I think it's unhealthy to sleep for 3-4 hours a day and you will be more productive if you sleep 8-9 (or more) hours a day.
Oh thank you very much for the explanation !!! Now you mention the y = k*x + b, it make a lot of sense, why couldn't I realize it sooner ... Again, thank you, I've looking for an answer for several hours. And for my sleep, just to share it with you guys, it worked well for me. I improve drastically in the last few day, and even get pass most of the first half section of USACO Guide Platinum section while clearing almost all problem except the "Hard" and above level. And I was a very inexperience competitive programmer before when I sleep for 8 hrs (like, I was once human too you know, but not now, as I've evolve into a nerd). Of course I don't mean to provide misleading info, the first few day was extremely hard. And also, get to Platinum, just mean I've expanded my knowledge by that much from a grey. It's still far too unrealistic to say that I can do well in USACO Silver, but I intended to get good by ANY MEANS. Finally, Happy New Year to you, sir, for saving me from several hrs spend thinking this problem without getting anywhere
No problem! Happy New Year to you too.