Open lxxue opened 6 years ago
I guess there is a bug in the implementation of Graham's Scan algorithm.
Try the following testcase: Input: { 0, 0 }, { 1, 1 }, { 2, 2 }, { 1, 4 } output: { 1, 4 }, { 2, 2 }, { 1, 1 }, { 0, 0 } correct output: { 1, 4 }, { 2, 2 }, { 0, 0 }
I believe the problem is in line 70: points[1] is not necessarily a vertex of convex hull if points[1] and points[2] have the same direction.
Btw: thank you for your wonderful blogs and readable code!
Yeah, the convex hull code doesn't even pass on CSES, like bruh.
avighnac
commented
1 year ago
I guess there is a bug in the implementation of Graham's Scan algorithm.
Try the following testcase: Input: { 0, 0 }, { 1, 1 }, { 2, 2 }, { 1, 4 } output: { 1, 4 }, { 2, 2 }, { 1, 1 }, { 0, 0 } correct output: { 1, 4 }, { 2, 2 }, { 0, 0 }
I believe the problem is in line 70: points[1] is not necessarily a vertex of convex hull if points[1] and points[2] have the same direction.
Btw: thank you for your wonderful blogs and readable code!