270. Circle Meets Box
A sprinkler waters every point within radius of its head at (xc, yc), so the watered region is the full disc: the circle together with everything inside it. A flower bed is the axis-aligned rectangle whose opposite corners are (x1, y1) and (x2, y2), with x1 < x2 and y1 < y2; the bed includes its border.
Return true if the disc and the bed share at least one point, where merely touching at a single point counts, and false otherwise. All inputs are integers. Compare squared distances with integers, never square roots. The check takes O(1) time and O(1) space.
Example 1
- Input:
- radius = 4xc = 9yc = 1x1 = 0y1 = 0x2 = 5y2 = 3
- Output:
- true
- Explanation:
The nearest rectangle point is (5,1), exactly 4 units from the centre, so the disc just reaches it.
Example 2
- Input:
- radius = 3xc = -6yc = 8x1 = -2y1 = 0x2 = 6y2 = 5
- Output:
- false
- Explanation:
The nearest point (-2,5) is at distance sqrt(16+9)=5, more than the radius 3.
Example 3
- Input:
- radius = 2xc = 1yc = 1x1 = -3y1 = -3x2 = 4y2 = 4
- Output:
- true
- Explanation:
The centre lies inside the rectangle, so the shapes certainly overlap.
Constraints
1 ≤ radius ≤ 104
-104 ≤ xc, yc, x1, y1, x2, y2 ≤ 104
x1 < x2 and y1 < y2
Squared distances reach 8*108 so use 64-bit arithmetic to be safe.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(1)
- Space
- O(1)