Sensors Inside a Triangular Zone
MediumMath & Geometry
Problem
A protected zone is the triangle with integer corners triangle = [[x1, y1], [x2, y2], [x3, y3]], listed in either clockwise or counter-clockwise order. Sensors stand at the integer points in points.
Return how many sensors lie inside the zone or on its boundary.
Example 1
- Input:
- triangle = [[0, 0], [4, 0], [0, 4]], points = [[1, 1], [2, 2], [3, 3], [0, 0], [-1, 0]]
- Output:
- 3
(1, 1) is inside, (2, 2) is on the slanted edge, (0, 0) is a corner. (3, 3) and (-1, 0) are outside.
Example 2
- Input:
- triangle = [[0, 0], [0, 4], [4, 0]], points = [[1, 1], [2, 2], [3, 3], [0, 0], [-1, 0]]
- Output:
- 3
Same zone, corners listed clockwise.
Constraints
- The triangle has positive area
- 1 ≤ points.length ≤ 10^5
- -10^6 ≤ all coordinates ≤ 10^6
Hint
Show the first hint
For a directed edge A → B, the sign of the cross product (B - A) × (P - A) tells you on which side of the edge P lies.
Walkthrough
How to approach it
01Clarify before coding
- Do points on the boundary count? Yes, edges and corners included.
- Is the corner order known? No: either orientation, so the test must not depend on it.
- Do intermediate values fit? Cross products are at most about 8 · 10^12 in magnitude, safe in JavaScript.
02Brute force
Compare the triangle's area with the sum of the areas of the three triangles P forms with the edges (equal means inside), computed with floating point.
Cost: O(n) too, but with doubled-area integers it works, while with Heron's formula and floats boundary points get misclassified.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.