It_Wasnt_Me's blog

help on 195D—Analyzing Polyline problem(Geometry problem)
By It_Wasnt_Me, 5 years ago, In English

https://mirror.codeforces.com/contest/195/problem/D I am so close to the solution but there is something that confuse me

the problem describe that $$$S(x)$$$ is sum of $$$n$$$ functions, the solution just use $$$F(x)$$$ for each line,

Should I consider $$$S(x)$$$ so I should sum all $$$k_i$$$ and $$$b_i$$$ ? https://mirror.codeforces.com/contest/195/submission/67170155 Anyone know why I am wrong?

Can anyone help me If he have explanation for the solution or explain the tutorial more because it is a bit unclear for me. :)

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

See, you are adding up all the lines of form y = kx + b so you are considering sum of functions = y1 + y2 + y3 ....etc but problem here is that you must notice that f = kx+ b is only true when kx+b > 0 Otherwise y = 0, in other words, all the ys will NOT CONTRIBUTE to the sum of functions always because maybe at some x, they are negative, at such an x they won't contribute. Only, when a particular y becomes positive, will it start contributing to the sum of functions.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    aha, I got you. but what make the solution works if I consider only $$$F(x)$$$, Could you explain the solution a bit more ?

    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I still stuck on this problem :( Could anyone help me

→ Reply