막대 돌리기

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

요약
단순 다각형 내부에서 막대가 시계 방향으로 회전하며 벽에 새 접점이 생길 때마다 그 점을 축으로 삼는다. 막대 끝 A의 최종 좌표를, 도중에 멈추면 그 순간의 좌표를 구한다.
난이도

어려움10점 중 9점

유형
기하, 시뮬레이션, 구현, 수학
정답자
아직 제출이 없습니다

문제

평면 위에 다각형 벽으로 둘러싸인 방이 있다. 그 안에서 길이 LL인 막대를 바통처럼 시계 방향으로 돌린다.

처음에 막대의 한쪽 끝(끝 A)은 (0,0)(0, 0)에, 반대쪽 끝(끝 B)은 (0,L)(0, L)에 놓여 있다. 이때 막대는 끝 A 한 점에서만 벽에 닿아 있다.

막대는 벽에 닿은 점 하나를 중심으로 시계 방향으로 돈다. 돌다가 막대의 다른 부분이 벽에 새로 닿으면 그 점이 새로운 회전 중심이 된다.

막대가 시계 방향으로 모두 2πR2\pi R 라디안을 돌았을 때 끝 A의 좌표를 구하라.

도중에 막대가 끼어 버리기도 한다. 벽에 닿아 있는 어느 점을 중심으로 잡아도 시계 방향으로 더 돌릴 수 없는 상태다. 이때는 회전이 거기서 끝나고, 그 자리의 끝 A 좌표가 답이다.

막대 길이 LL이 ε\varepsilon(∣ε∣<0.00001|\varepsilon| < 0.00001)만큼 달라져도 최종 좌표 (x,y)(x, y)는 0.00050.0005보다 크게 변하지 않는다고 가정해도 된다.

입력

입력은 여러 데이터 집합으로 이루어진다. 데이터 집합은 100개를 넘지 않는다. 입력의 끝은 0 0 0으로 표시한다.

각 데이터 집합의 형식은 다음과 같다.

L R N
X1 Y1
X2 Y2
...
XN YN

LL은 막대의 길이다. 막대는 도중에 끼지 않는다면 2πR2\pi R 라디안만큼 돈다. NN은 벽을 이루는 다각형의 꼭짓점 개수다.

다각형의 꼭짓점은 반시계 방향으로 주어진다. 다각형은 단순하다. 즉 경계가 자기 자신과 교차하거나 닿는 일이 없다.

NN과 XiX_i, YiY_i는 정수이고 LL과 RR은 소수다. 값의 범위는 다음과 같다.

  • 1.0≤L≤500.01.0 \le L \le 500.0
  • 1.0≤R≤10.01.0 \le R \le 10.0
  • 3≤N≤1003 \le N \le 100
  • −1000≤Xi≤1000-1000 \le X_i \le 1000
  • −1000≤Yi≤1000-1000 \le Y_i \le 1000
  • X1≤−1X_1 \le -1, Y1=0Y_1 = 0
  • X2≥1X_2 \ge 1, Y2=0Y_2 = 0

출력

데이터 집합마다 끝 A의 최종 좌표를 한 줄에 출력한다. 채점은 출력을 그대로 비교하므로 좌표를 정수로 바꿔서 적는다. xx와 yy를 각각 1000배 한 값을 가장 가까운 정수로 반올림해, 두 정수를 공백 하나로 구분해 출력한다.

입력 데이터에서는 1000x1000x와 1000y1000y가 반올림 경계, 즉 정수에 0.50.5를 더한 값에서 10−410^{-4} 이상 떨어져 있다. 따라서 반올림 결과는 하나로 정해진다.

예제1

  1. 예제 1

    입력
    4.0 2.0 8
    -1 0
    5 0
    5 -2
    7 -2
    7 0
    18 0
    18 6
    -1 6
    4.0 2.0 4
    -1 0
    10 0
    10 12
    -1 12
    4.0 1.0 7
    -1 0
    2 0
    -1 -3
    -1 -8
    6 -8
    6 6
    -1 6
    4.0 2.0 6
    -1 0
    10 0
    10 3
    7 3
    7 5
    -1 5
    5.0 2.0 6
    -1 0
    2 0
    2 -4
    6 -4
    6 6
    -1 6
    6.0 1.0 8
    -1 0
    8 0
    7 2
    9 2
    8 4
    11 4
    11 12
    -1 12
    0 0 0
    
    예상 출력
    16000 0
    10000 7464
    586 -5414
    8000 0
    6000 0
    9528 4000