Funcia
Lv.4convex-hullgeometrysorting

Convex Hull Vertices

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Trees stand at points[i] = [x, y] (duplicates allowed). Return the number of vertices of their convex hull: points lying on a straight edge do not count, all-identical points give 1, and collinear points give 2.

Examples

pointsresult
[[0, 0], [2, 0], [2, 2], [0, 2], [1, 1], [1, 0]]4
[[0, 0], [1, 1], [2, 2], [3, 3]]2
[[5, 5], [5, 5]]1

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(points: int[][]) → int

Constraints

  • 1≤1 \le points.length ≤200,000\le 200{,}000, −109≤x,y≤109-10^9 \le x, y \le 10^9

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

pointsExpected
[[0,0],[2,0],[2,2],[0,2],[1,1],[1,0]]4
[[0,0],[1,1],[2,2],[3,3]]2
[[5,5],[5,5]]1

Hint

Hint

Andrew's monotone chain: sort, dedupe, build lower and upper hulls popping while the cross product is <= 0 (so edge points are dropped). Use 64-bit cross products (each product reaches 4×10184 \times 10^{18}), never doubles. Gift wrapping is O(NH)O(NH).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)234 msestimated
C++ (GCC, gnu++23)234 msderived
Python 3.131000 msderived
Java 252058 msderived
Kotlin 2.4 (JVM)1468 msestimated
C# 14 (.NET 10)1468 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness409verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.