만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

마라톤을 관람하자

시간 제한8초메모리 제한1024 MB

요약
원점에서 (a, b)까지 이어진 선분에서 가장 가까운 정수 격자점을 구합니다. 거리가 같으면 X, Y가 작은 점을 출력합니다.
난이도

보통10점 중 6점

유형
정수론, 기하
정답자
아직 제출이 없습니다

문제

육상 경기 팬인 당신은 어느 마라톤 대회를 현장에서 관람하기로 했다. 이 대회에서는 XYXY 평면 위의 원점과 점 (a,b)(a, b)를 잇는 선분이 마라톤 코스가 된다. 또한 대회 중 교통 통제 때문에, 관람은 XX 좌표와 YY 좌표가 모두 정수인 점 가운데 마라톤 코스 위에 있지 않은 점에서만 할 수 있다.

당연히 가능한 한 마라톤 코스에 가까운 지점에서 보고 싶다. 위 조건을 만족하는 점 가운데 마라톤 코스까지의 유클리드 거리가 가장 가까운 점을 구하라. 그런 점이 여러 개라면 그중 XX 좌표가 가장 작은 점을 구하라. 그런 점도 여러 개라면 그중 YY 좌표가 가장 작은 점을 구하라.

입력

입력은 300,000300{,}000개 이하의 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식으로 주어진다.

aa bb

aa와 bb는 모두 11 이상 10910^9 이하의 정수이며, 마라톤 코스의 한쪽 끝점 좌표를 나타낸다.

입력의 끝은 0 0 두 개로 이루어진 줄이다.

출력

각 데이터셋에 대해 이 대회를 관람하기에 가장 좋은 지점의 XX 좌표와 YY 좌표를 공백으로 구분하여 한 줄에 출력하라.

예제1

  1. 예제 1

    입력
    2 3
    2 9
    7 2
    9 8
    4 9
    6 6
    5 7
    9 1
    5 3
    65537 735134400
    0 0
    
    예상 출력
    1 1
    1 4
    3 1
    1 1
    1 2
    0 1
    2 3
    1 0
    2 1
    23788 266832127