1690 - 두개의 문

• Submit
• Status
• Discuss
• Summary

Description

당신은 지금 정사각형 모양의 이상한 방에 갇혀버렸다. 이 방의 구조는 굉장히 특이한데, 방을 (0,0)에서 (10,10)에 이르는 사각형으로 모델링했을 때, 방 사이의 벽은 항상 y축에 평행하며, 그 벽에는 항상 2개의 문짝이 달려있다는 점이 특이했다.

현재 당신의 위치는 (0,5) 이고, (10,5)에 위치한 출구를 통해 밖으로 빠져나가고 싶다. 중간에 있는 벽들은 그냥 지나갈 수 없고 항상 문으로만 출입이 가능하다고 할 때, 출구까지 도달하는데 필요한 거리의 최소값을 구하시오.

위의 예제의 경우  x = 7 에 해당하는 벽에 의해 막히므로, 출구까지 직진할 순 없고 문 끝을 걸쳐서 통과해야 한다.

Input

입력은 여러개의 테스트데이터로 이루어져있다.

각 데이터의 첫번째 줄에는 벽의 개수 n이 주어진다. (0 ≤ n ≤ 18)

그 다음 n개의 줄에 걸쳐 5개의 실수값 x y1 y2 y3 y4 가 주어진다. x는 벽이 위치한 x좌표를 의미하며, y1~y2 사이에 문이, y3~y4 사이에 문이 있음을 의미한다. y좌표는 오름차순으로 주어진다. 입력으로 들어오는 벽의 정보는 x좌표의 오름차순으로 주어진다. 좌표들은 0에서 10 사이이다.

n으로 -1이 들어오면 입력을 종료한다.

Output

각 테스트데이터마다 한줄에 하나씩 이동거리의 최소값을 반올림하여 소수점 둘째자리까지 출력한다.

Sample Input

1
5 4 6 7 8
2
4 2 7 8 9
7 3 4.5 6 7
-1

Sample Output

10.00
10.06

Source

Regionals 1996, North America - Mid-Central USA