روز
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
روز
ساعت
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
ساعت
دقیقه
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
دقیقه
ثانیه
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
ثانیه
  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

“A big surprise is coming on the next Thursday!”, the young mayor of TetrisCity announced in the social media. TetrisCity is the most populous and modern city in Neverland constructed on a flat area with endless clusters of high-rise buildings packed so closely together that they resemble a game of Tetris. uildings look like axisparallel boxes constructed on the ground and they are disjoint (they do not even touch each other).

The big surprise announced by the mayor is going to be a special delivery service using drones. The drones used in this service are a generation of quadcopters which can physically move only in one of x,y,x, y, and zz directions. So, the distance traveled by a drone is the sum of distances traveled by it in each axis. The young mayor now has ordered to make the drones smart by equipping them with a software that computes the shortest path from any source to any destination avoiding the buildings. Your job is to develop this software.

ورودی

The first line of the input contains an integer nn (0n1000 \leq n \leq 100), specifying the number of buildings in the TetrisCity. Each of the next nn lines contains 5 space-separated integers x,y,x,y,x, y, x', y', and hh specifying a building: the coordinates (x,y)(x, y) and (x,y)(x', y') respectively specify the west-south corner and the east-north corner of the building, and hh determines its height. It is guaranteed that the volume of the building is not zero. The source and destination appear at the end of the input in two separated lines; each containing x,y,x, y, and zz coordinates. All numbers in the input are non-negative integers being at most 100,000100, 000. It is guaranteed that the source and destination are outside the buildings (they can be on the boundary of buildings). The shortest path can touch buildings and it is assumed that a drone looks like a point.

خروجی

In the output, print the length of the shortest path from the source to the destination avoiding the buildings.

مثال

ورودی نمونه ۱

1
1 1 11 21 40
5 0 5
6 23 8
Plain text

خروجی نمونه ۱

35
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.