286. Rope Around Posts
A fence builder has planted n distinct posts at integer positions posts[i] = [x, y] and pulls one rope tight around the whole group. A post touches the rope if it is a corner of the rope or sits exactly on a straight stretch of rope between two corners. Return every post that touches the rope, including posts lying on straight sides.
Return the posts as an int[][] sorted by x ascending, breaking ties by y ascending; the answer is compared exactly in this order. If all posts are collinear, the rope runs along them and every post touches it; with 1 to 3 posts you simply return them all, sorted. Target O(n log n): testing every pair of posts against every post is cubic and times out at n = 1100.
Example 1
- Input:
- posts = [[0,0],[4,0],[2,0],[2,3],[2,1],[1,1]]
- Output:
- [[0,0],[2,0],[2,3],[4,0]]
- Explanation:
The rope forms a triangle; the post at (2,0) lies on its bottom side, while (2,1) and (1,1) are inside.
Example 2
- Input:
- posts = [[7,-3],[1,1],[4,-1]]
- Output:
- [[1,1],[4,-1],[7,-3]]
- Explanation:
All three posts are collinear, so the rope lies along them and all touch it, listed by increasing x.
Example 3
- Input:
- posts = [[0,0],[0,6],[6,0],[6,6],[3,3],[3,0],[0,3]]
- Output:
- [[0,0],[0,3],[0,6],[3,0],[6,0],[6,6]]
- Explanation:
The square fence has extra posts at (3,0) and (0,3) on its sides; the centre post (3,3) is inside.
Constraints
1 ≤ posts.length ≤ 1100
-104 ≤ x, y ≤ 104
All posts are distinct.
Cross products stay below 109, so 64-bit integers (or JavaScript numbers) are exact.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)