オリエンテーリング
시간 제한8초메모리 제한1024 MB
원점에서 출발해 겹치지 않는 N개의 축 평행 직사각형을 순서대로 지나 다시 원점으로 돌아오는 최단 이동 거리를 구한다.
문제
あなたは，オリエンテーリングの競技に参加することになった．この競技では，XY 平面の原点から出発し，N 個のチェックポイントを順番に通過し，再び原点に戻ってくればクリアとなる．あなたの目的は，クリアのための移動距離を最小化することである．
ここで，この競技における各チェックポイントは，すべての辺が座標軸に平行な長方形である．すなわち，4 点 (Li, Bi), (Ri, Bi), (Ri, Ti), (Li, Ti) を頂点とする長方形の辺上および内部を，i 番目のチェックポイントと呼ぶ．形式的には，以下の二つの条件をともに満たしたとき，i 番目のチェックポイントを通過したとみなす．
- 条件 1: i ≥ 2 であるならば，i-1 番目のチェックポイントはすでに通過済みである．
- 条件 2: あなたが現在いる座標 (x, y) が，Li ≤ x ≤ Ri および Bi ≤ y ≤ Ti を満たす．
条件 1 を満たさない状態であるチェックポイント内に立ち入ったり，すでに通過済みのチェックポイント内に再度立ち入ったりしてもよいが，その場合は何も起きない．
あなたは，この二次元平面上を自由に動くことができる．あなたが原点から出発し，N 個のチェックポイントを順番に通過し，再び原点に戻ってくるまでの移動距離の最小値を求めよ．
なお，この問題において，チェックポイントは以下の制約を満たす．
- どの二つのチェックポイントも，点を共有しない．
- いずれのチェックポイントも，原点を含まない．
입력
入力は 50 個以下のデータセットからなる．各データセットは次の形式で表される．
N
L1 R1 B1 T1
...
LN RN BN TN
1 行目には整数 N が与えられる．N はこのオリエンテーリングにおけるチェックポイントの数であり，1 ≤ N ≤ 9 を満たす．
続く N 行には，N 個のチェックポイントの情報が与えられる．このうち i 番目の行には整数 Li, Ri, Bi, Ti が与えられ，それぞれこのチェックポイントの左端の X 座標，右端の X 座標，下端の Y 座標，上端の Y 座標を表す．-10,000 ≤ Li < Ri ≤ 10,000 および -10,000 ≤ Bi < Ti ≤ 10,000 を満たすことが保証される．どの二つのチェックポイントも点を共有せず，また，いずれのチェックポイントも原点を含まないことが保証される．
入力の終わりは 1 つのゼロからなる行で表される．
출력
各データセットに対し，あなたがこの競技をクリアするために必要な移動距離の最小値を，一行に出力せよ．出力は相対誤差または絶対誤差が 10-6 以下であれば許容される．