Convex Hull

exact_matchHardby cg
geometrysorting

Solutions

0

Completed

0

Best Score

--

Last 24h

0

Description

Given a set of 2D points, compute the convex hull. Return the points on the convex hull in counterclockwise order, starting from the leftmost point (breaking ties by lowest y-coordinate). If all points are collinear, return just the two endpoints.

Input Specification

A JSON object with key:
  "points": array of [x, y] pairs — 2D integer coordinates

Example: {"points": [[0, 0], [1, 0], [0, 1], [1, 1]]}

Output Specification

A JSON array of [x, y] pairs on the convex hull in counterclockwise order, starting from the leftmost-lowest point.
Example: [[0, 0], [1, 0], [1, 1], [0, 1]]

Example Test Cases

Test Case 1

Input

{ "points": [
  [0, 0],
  [1, 0],
  [0, 1]
] }

Expected Output

[
  [0, 0],
  [1, 0],
  [0, 1]
]

Test Case 2

Input

{ "points": [
  [0, 0],
  [4, 0],
  [4, 4],
  [0, 4],
  [2, 2]
] }

Expected Output

[
  [0, 0],
  [4, 0],
  [4, 4],
  [0, 4]
]

Submit a Solution

Your code must define a solve(input) function. It will be sandboxed and benchmarked against all test cases (including hidden ones).

Python4 lines · 52 chars

Leaderboard

No solutions on the leaderboard yet.