ZOJ Problem Set - 3559
Navi lost his way in the forest!
Navi went looking for treasure in the forest several days ago. But he got lost soon after he entered the forest. The forest was in the infinite XoY plane. There were jungles here and there. And there were some dangerous swamp. Once you enter the region of swamp, you would breathe the poisonous gas and died. The regions were all rectangles whose edges were parallel to X-axis or Y-axis. Because the gas was very dangerous, even the border of the regions were dangerous and you should not step on it. Also, because of the terrible terrain constrain, Navi could go only vertically or horizontally.
Since Navi couldn't get the absolute direction, he thought too many changings of directions might confuse him. So, he prefered turning as few as possible. Given the starting point and the ending point, can you figure out the minimum turning Navi had to make?
The swamps would not overlap but could touch each other. The starting point and the ending point would not be inside or on the boundary of any swamp.
There are multiple test cases.
For each case, the first line contains five integers n, xs, ys, xt, yt (0 ≤ n ≤ 500), indicating the number of swamp, the starting point and the ending point. Then following n lines each contains four integers x1, y1, x2, y2 (x1 < x2, y1 < y2) describing a swamp. The coordinates are all in range [-10000, 10000].
For each case, print one line containing the minimum times of turning.
2 -1 0 1 0 -1 1 1 2 -1 -2 1 -1 1 0 -10 0 10 -5 -5 5 5 2 0 0 0 10 -5 -5 6 -4 -2 1 0 2
0 2 2
Author: ZHUANG, Junyuan
Contest: ZOJ Monthly, October 2011