FastPrep
Problem · Math

Cyber Beacon Detection

Learn this problem
● MediumRippling logoRipplingFULLTIMEOA

Problem statement

A network is modeled as every integer-coordinate node inside an axis-aligned rectangle whose bottom-left corner is (x1, y1) and top-right corner is (x2, y2). Both rectangle boundaries are inclusive.

A beacon centered at (beaconX, beaconY) completely illuminates a node when the node's Euclidean distance from the beacon is at most radius.

Return the number of network nodes that are completely illuminated.

Equivalently, count the integer pairs (x, y) that satisfy both rectangle bounds and (x - beaconX)^2 + (y - beaconY)^2 <= radius^2.

Function

countIlluminatedNodes(x1: int, y1: int, x2: int, y2: int, beaconX: int, beaconY: int, radius: int) → long

Examples

Example 1

x1 = -2y1 = -2x2 = 2y2 = 2beaconX = 0beaconY = 0radius = 1return = 5

The illuminated nodes are the center and its four axis-adjacent neighbors.

Example 2

x1 = 0y1 = 0x2 = 2y2 = 2beaconX = 0beaconY = 0radius = 2return = 6

The six points are (0,0), (0,1), (0,2), (1,0), (1,1), and (2,0).

Example 3

x1 = 5y1 = 5x2 = 7y2 = 7beaconX = 0beaconY = 0radius = 2return = 0

The rectangle does not intersect the illuminated circle.

Constraints

  • -10^9 <= x1 <= x2 <= 10^9
  • -10^9 <= y1 <= y2 <= 10^9
  • -10^9 <= beaconX, beaconY <= 10^9
  • 0 <= radius <= 10^9
  • x2 - x1 <= 2 * 10^5

More Rippling problems

drafts saved locally
public long countIlluminatedNodes(int x1, int y1, int x2, int y2, int beaconX, int beaconY, int radius) {
    // write your code here
}
x1-2
y1-2
x22
y22
beaconX0
beaconY0
radius1
expected5
checking account