Ctrl K

Rope Around the Posts

Hard
Posts are driven into a field, and posts[i] = [x, y] gives the position of post i. A rope of the smallest possible length is stretched around the plot so that every post is inside it or on the rope itself. Return the coordinates of every post that lies exactly on the rope, at a corner of the enclosure or along one of its sides. The order of the answer does not matter.
Example 1
posts=[[0, 0], [4, 0], [4, 3], [0, 3], [2, 1], [2, 3]] → [[0, 0], [4, 0], [4, 3], [2, 3], [0, 3]]

The rope follows the rectangle with corners (0, 0), (4, 0), (4, 3), (0, 3). Post (2, 3) sits on the top side and touches the rope too; (2, 1) is inside.

Example 2
posts=[[5, 5], [1, 1], [3, 3]] → [[5, 5], [1, 1], [3, 3]]

All posts lie on one line, so the rope passes through each of them.

Example 3
posts=[[7, 2]] → [[7, 2]]
Constraints
  • 1 ≤ len(posts) ≤ 3000
  • posts[i] = [x, y], 0 ≤ x, y ≤ 100
  • All positions are distinct
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsStars on One Straight Line HardDoes the Robot Cross Its Trail HardWater as Many Plants as Possible HardA Depot Close to All Shops HardBest View for a Turning Camera Hard
loading Python…
Input
posts=[[0, 0], [4, 0], [4, 3], [0, 3], [2, 1], [2, 3]]
Expected
[[0, 0], [4, 0], [4, 3], [2, 3], [0, 3]]

Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.