Jeroen operates a warehouse storage facility for the North Western Electrical Resource Company (NWERC). When a customer places an order with NWERC, this order is conveyed to the warehouse. Jeroen’s task is to then find the products ordered, pack them into a box, and ship them to the customer.
NWERC has an unusual warehouse policy: the products are not arranged in any particular order, and are strewn all over the place. However, it is possible for Jeroen to do his job because each product is tracked using RFID technology3. Specifically, each product is assigned a wireless RFID chip as soon as it enters the warehouse, and sensors located on the warehouse ceiling are used to automatically track the products.
By default, each sensor has a range of r units – that is, it can read any RFID chip that is located at most r units from it in a straight line. However, if the line segment between a sensor and a product intersects with or touches x walls, the range of the sensor is reduced by x units in that direction. Furthermore, the sensors may fail to read an RFID chip due to interference from other sensors, so the distance between any pair of sensors in the warehouse is guaranteed to be at least r units. You may further assume that no sensor or product is placed on a wall.
Jeroen now wants to determine, for each product, which sensors can read its RFID chip. Can you help him?