OA: Food delivery system

A delivery app knows where each restaurant is on a flat map and what each one sells. Couriers ride in a straight line at speed 1, so the delivery time from a restaurant is simply the straight-line (Euclidean) distance from the restaurant to the customer.

Implement FoodDeliverySystem:

• FoodDeliverySystem(restaurants: list[tuple[str, int, int]], menu: list[tuple[str, str, int]])
  • restaurants: (name, x, y) for each restaurant; names are unique.
  • menu: (restaurant, item, price) rows. If a restaurant lists the same item twice, the later price wins. A row naming a restaurant that isn't in restaurants raises ValueError.
• best_options(x: int, y: int, item: str) -> tuple[int, float] | None: for a customer at (x, y), return (lowest_price, fastest_time) over all restaurants that sell item. The two numbers may come from different restaurants. Return None if nobody sells it.

fd = FoodDeliverySystem(
    [("Noodle Bar", 0, 0), ("Pho Place", 3, 4), ("Deli", 10, 0)],
    [("Noodle Bar", "ramen", 12), ("Pho Place", "ramen", 9), ("Pho Place", "pho", 11),
     ("Deli", "sandwich", 7), ("Noodle Bar", "ramen", 14)],   # Noodle Bar raises its ramen price
)
fd.best_options(0, 0, "ramen")      # (9, 0.0)    cheapest at Pho Place, fastest from Noodle Bar
fd.best_options(6, 8, "ramen")      # (9, 5.0)    Pho Place is both
fd.best_options(10, 3, "sandwich")  # (7, 3.0)
fd.best_options(1, 1, "sushi")      # None

The app has thousands of restaurants and a big menu, and best_options is called constantly. Organise the menu by item when the system is built, so a query only looks at the restaurants that sell that item instead of scanning every menu row.