The Big Surprise
Time limit2sMemory limit512 MB
Given up to 100 axis-aligned boxes, find the shortest rectilinear (Manhattan) 3D path between two points that avoids the boxes' interiors.
- Level
Hard8 of 10
- Topics
- Geometry, Shortest path, Graph
- Solved
- No attempts yet
문제
The mayor of TetrisCity announced on social media: "A big surprise is coming on the next Thursday!" TetrisCity is the most populous and modern city in Neverland. It is built on a flat area with clusters of high-rise buildings packed so closely that they resemble a game of Tetris. Each building is an axis-parallel box standing on the ground. The buildings are disjoint, and they do not even touch each other.
The big surprise is a special delivery service that uses drones. The drones are quadcopters that can move in only one of the x, y, and z directions. The distance a drone travels is therefore the sum of its distances along each axis. The mayor has ordered software that computes the shortest path from any source to any destination while avoiding the buildings. Your job is to develop this software.
Input
The first line contains an integer n (0 ⩽ n ⩽ 100), the number of buildings. Each of the next n lines contains five space-separated integers x, y, x′, y′, and h. Here (x, y) is the west-south corner and (x′, y′) is the east-north corner of the building, and h is its height. The volume of every building is not zero.
The source and destination appear at the end of the input, on two separate lines. Each line contains the x, y, and z coordinates of a point. All numbers in the input are non-negative integers at most 100 000. The source and destination are outside the buildings, though they may lie on a building's boundary. The shortest path may touch buildings, and a drone is modeled as a point.
Output
Print the length of the shortest path from the source to the destination that avoids the buildings.