cho.sh

Dijkstra Is Playing At My House

서로 겹치지 않는 최대 250,000개의 축 평행 직사각형 장애물이 있는 평면에서 두 점 사이의 맨해튼 최단 경로 길이를 구한다. 장애물의 경계는 지날 수 있다.

어려움9최단 경로그래프정렬기하아직 제출이 없습니다시간 제한3초메모리 제한1024 MB

문제

To celebrate your team's victory at ICPC World Finals, Edsger W. Dijkstra (The inventor and namesake of Dijkstra's algorithm) will throw a fabulous party at your house in New York City. The party starts in 4 hours, so he should better start moving.

New York City is modeled as a 2-dimensional plane. Dijkstra is now in coordinate (s_x, s_y)(s\_x,\ s\_y), and your house is located in coordinate (e_x, e_y)(e\_x,\ e\_y). Dijkstra should come to your house by only moving in a direction parallel to the coordinate axes (you remember the Manhattan distance, right?). Also, there are NN skyscraper in an axis-parallel rectangular shape, which you can pass through its boundary, but cannot pass through anywhere strictly inside of it.

You got a phone call from Dijkstra, saying that it's too hard for him to compute the shortest path between his location and your house. Somehow, he is losing his edge. However, that's not bad news, because it's a chance for you to be cool in front of the great Dijkstra. Can you?

It is guaranteed that all xx coordinates are distinct and all yy coordinates are distinct. It is also guaranteed that no pair of rectangles overlap. It is also guaranteed that your house and Dijkstra's starting location are not inside of any rectangles.

입력

The first line contains five space-separated integers NN, s_xs\_x, s_ys\_y, e_xe\_x, e_ye\_y.

The ii-th line of next NN lines contain four space-separated integers a_ia\_i, b_ib\_i, c_ic\_i, d_id\_i. This indicates that ii-th skyscraper is a rectangle with its four corners located in (a_i, b_i), (a_i, d_i), (c_i, b_i), (c_i, d_i)(a\_i,\ b\_i),\ (a\_i,\ d\_i),\ (c\_i,\ b\_i),\ (c\_i,\ d\_i).

출력

Print the length of the shortest path between Dijkstra's location and your house, using the Manhattan metric.

제한

  • 1≤N≤250,0001 \le N \le 250\\,000

  • 0≤s_x, s_y, e_x, e_y≤1080 \le s\_x,\ s\_y,\ e\_x,\ e\_y \le 10^8

  • 0≤a_i<c_i≤1080 \le a\_i < c\_i \le 10^8 (1≤i≤n1 \le i \le n)

  • 0≤b_i<d_i≤1080 \le b\_i < d\_i \le 10^8 (1≤i≤n1 \le i \le n)

  • Let X=s_x, e_x, a_1, a_2, ⋯ , a_N, c_1, c_2, ⋯ , c_NX = \\{s\_x,\ e\_x,\ a\_1,\ a\_2,\ \cdots,\ a\_N,\ c\_1,\ c\_2,\ \cdots,\ c\_N\\}, all elements in XX are distinct.

  • Let Y=s_y, e_y, b_1, b_2, ⋯ , b_N, d_1, d_2, ⋯ , d_NY = \\{s\_y,\ e\_y,\ b\_1,\ b\_2,\ \cdots,\ b\_N,\ d\_1,\ d\_2,\ \cdots,\ d\_N\\}, all elements in YY are distinct.

  • No pair of rectangles share a common point.

  • Dijkstra's location and your house's location are not in any of the rectangles.