Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

MarioYC's blog

Convex Hull Trick
By MarioYC, 15 years ago, In English

Hope it can be useful to other people:


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

15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Can this be used to find the highest point of the lowest envelope?
(i will use it in graphical method to solve two-person-zero-sum game (2Xn matrix) )
If yes , then plz tell how ? (if you have free time  :) ) 
→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Hi, I haven't finished reading it, but decided to share it, since I haven't heard about it before. Now, about the highest I think it wouldn't be hard to find if you have the lines which form the segments that form the lowest envelope, as far as I understand the method gives you that. :)
    → Reply