Erect The Fence


  • 0

    Click here to see the full article post


  • 0
    H

    I just didn't understand the "the line qr should be having more slope than the line pq", so i find maybe the conduct product is a good explanation. if conduct product of pq and pr is positive, then the lines pq, pr is anticlockwise direction.


  • 0

    @hell0123 The meaning of this line is that the line qr should be obtained by doing an anticlockwise rotation of the line pq, then only the point q can be more counter-clockwise to p than r. For the line qr to be obtained by anitclockwise rotation of pq, qr's slope should be more than pq's slope.


  • 0
    K

    why is this statement true: "in order for the point q to be more counterclockwise to p than the point r, the line qr should be having more slope than the line pq."?

    Isn't in fact wrong in the example? the slope of qr is negative while the slope of pq is positive.


  • 0

    @kevinchacon @hell0123 I have updated the statement. I hope the current explanation seems more logical.


  • 0
    H

    @vinod23 ok, thank you.


  • 0
    K

    @vinod23 Thanks :)


  • 0
    B

    Solution listed under Jarvis Algorithm failed this test case:
    [[1,2],[2,2],[4,2],[5,2]]
    Expected answer : [[1,2],[5,2],[4,2],[2,2]]
    Wrong answer: [[2,2],[4,2],[5,2],[2,2],[4,2],[1,2]]


  • 0

    @bobw Thanks for pointing it out. I have updated the code. Please have a look.


  • 0
    B

    @vinod23 Thanks :)


  • 0
    Y

    In monotone chain appoach, what are the cases so we need to create new HashSet?
    Is it just to avoid duplication of first point that will be added in the end? Maybe we can just do hull.pop() before returning the result


  • 0

    @ykvarts We need hashset because of collinear points. Consider the case- input contains only three collinear points. Then left-right scan and right-scan give the same result. Thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.