Convex Hull Vertex Count
MediumMathGeometrySortingGraphMatrix
Description
Given a list of 2D points with integer coordinates, return the number of distinct vertices of their convex hull. Collinear points on hull edges are not counted as hull vertices.
Examples
Input:
points = [[0,0],[1,0],[0,1],[1,1]]Output:
4Explanation:
Unit square has 4 hull vertices.
Input:
points = [[0,0],[1,1],[2,2]]Output:
2Explanation:
All collinear; only 2 distinct extreme points.
Input:
points = [[0,0],[3,0],[3,3],[1,1]]Output:
3Explanation:
Inner point doesn't lie on hull.
Constraints
- •
1 ≤ points.length ≤ 500 - •
-10⁴ ≤ coords ≤ 10⁴