아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

레일 위의 로봇

시간 제한10초메모리 제한128 MB

요약
평면 위 최대 100개의 선분이 주어질 때, 시작점과 시작 방향에서 목표점과 목표 방향까지 가는 최단 경로를 구하되, 교차점에서의 회전은 90도 이하여야 한다.
난이도

어려움10점 중 8점

유형
그래프, 기하, 최단 경로, 구현
정답자
아직 제출이 없습니다

문제

카렐(Karel)은 아주 큰 홀에 서 있는 기계 로봇으로, 바닥에 놓인 레일 시스템을 따라 이동한다. 각 레일은 두께를 0으로 볼 수 있을 만큼 가느다란 곧은 선분이며, 레일끼리는 서로 교차하거나 겹칠 수도 있다.

카렐은 두 레일이 공유하는 임의의 점에서 한 레일에서 다른 레일로 갈아탈 수 있다. 다만 기술적 한계 때문에, 한 점에서 카렐이 방향을 트는 각도는 90도를 넘을 수 없다. 즉 경로의 모든 꺾임은 직각이거나 그보다 완만해야(둔각이어야) 한다. 그보다 급하게 꺾는 것은 불가능하므로, 어떤 교차점에서는 곧바로 꺾지 못하고 더 먼 길로 돌아가야 한다.

시작 위치에서 목표 위치까지 카렐이 이동할 수 있는 가장 짧은 경로의 길이를 구하여라.

입력

입력은 여러 개의 시나리오로 이루어진다.

각 시나리오는 레일 선분의 개수를 나타내는 양의 정수 RR (1≤R≤1001 \le R \le 100)이 적힌 줄로 시작한다. 이어지는 RR개의 줄에는 각각 네 정수 x1x_1, y1y_1, x2x_2, y2y_2가 주어지며, 이는 한 선분의 두 끝점의 좌표이다. 모든 좌표는 −10000-10000 이상 1000010000 이하이고, 모든 선분의 길이는 0이 아니다.

마지막 시나리오 다음에는 0 하나만 있는 줄이 온다.

카렐은 항상 첫 번째 선분의 첫 번째 점(그 선분의 시작점)에서 출발하며, 처음에는 그 첫 번째 선분의 방향을 바라보고 있다. 따라서 첫 이동은 그 방향이거나, 그 방향에서 90도 이내로 벗어난 방향이어야 한다.

목표점은 시나리오에서 마지막으로 주어진 점(마지막 선분의 끝점)이며, 시작점과 항상 다르다. 카렐은 목표점에 도달해야 할 뿐 아니라, 마지막 선분의 방향을 바라본 채로 멈춰야 한다. 마지막 선분을 따라 도착해도 되고, 다른 선분을 따라 도착해도 되지만 그 방향이 마지막 선분의 방향에서 90도 이내로만 벗어나야 한다.

출력

각 시나리오마다 위의 모든 조건을 만족하는 가장 짧은 경로의 길이를, 소수점 아래 정확히 세 자리로 반올림하여 한 줄에 출력한다(뒤에 불필요한 0이 붙을 수 있다). 목표점에 전혀 도달할 수 없으면 대신 unreachable을 출력한다.

예제3

  1. 예제 1

    입력
    5
    1 5 2 1
    1 0 6 4
    1 1 5 1
    5 1 4 5
    1 2 4 5
    2
    1 1 2 1
    3 3 4 3
    0
    
    예상 출력
    9.541
    unreachable
    
  2. 예제 2

    입력
    1
    0 0 3 4
    0
    
    예상 출력
    5.000
    
  3. 예제 3

    입력
    2
    0 0 2 0
    2 0 2 2
    0
    
    예상 출력
    4.000