당구대

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

요약
당구공이 목표 지점에 도달하기 전에 쿠션에 정확히 N번 부딪혀야 할 때, 이동 거리의 최솟값을 구한다. 모서리에 맞으면 두 번으로 센다.
난이도

어려움10점 중 8점

유형
기하, 수학, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

직사각형 당구대 위에 흰색 공과 빨간색 공이 하나씩 놓여 있다. 흰색 공은 빨간색 공을 맞추기 전에 쿠션(당구대의 네 모서리)을 정확히 NN번 맞춰야 한다. 이러한 경로 중에서 흰색 공이 이동한 거리의 최솟값을 구하여라.

  • 쿠션에 부딪힐 때 입사각과 반사각은 항상 같다.
  • 공의 지름은 무시한다(공을 점으로 본다).
  • 당구대의 한 꼭짓점을 원점으로 두고, 네 모서리는 모두 xx축 또는 yy축에 평행하다.
  • 공이 당구대의 꼭짓점(구석)에 맞으면 쿠션을 22번 맞춘 것으로 센다.
  • 빨간색 공을 맞추기 직전까지 쿠션을 맞춘 횟수의 합은 정확히 NN이어야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 공백으로 구분된 일곱 개의 정수로 이루어진 한 줄이다.

L W CX CY TX TY N
  • LL과 WW는 당구대의 가로와 세로 길이이다 (2≤L,W≤1002 \le L, W \le 100).
  • (CX,CY)(CX, CY)는 흰색 공의 좌표, (TX,TY)(TX, TY)는 빨간색 공의 좌표이다 (0<CX,TX<L0 < CX, TX < L, 0<CY,TY<W0 < CY, TY < W).
  • 두 공의 위치는 서로 다르다. 즉 (CX,CY)≠(TX,TY)(CX, CY) \ne (TX, TY)이다.
  • NN은 빨간색 공을 맞추기 전에 맞춰야 하는 쿠션의 수이다 (0≤N≤1000 \le N \le 100).

입력의 마지막 줄에는 00이 일곱 개 주어지며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 흰색 공이 이동한 거리의 최솟값을 한 줄에 하나씩 출력한다. 값은 소수점 아래 넷째 자리에서 반올림하여 소수점 아래 셋째 자리까지 출력한다.

예제2

  1. 예제 1

    입력
    20 15 10 1 12 1 1
    10 20 1 2 7 16 2
    0 0 0 0 0 0 0
    
    예상 출력
    2.828
    19.698
    
  2. 예제 2

    입력
    10 10 2 2 8 8 0
    0 0 0 0 0 0 0
    
    예상 출력
    8.485