배트 위치 잡기

면접 대비

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

요약
자신으로부터 100 이상 떨어진 포인터들의 무게중심과 일치하는 점을 찾아 좌표를 반올림해 출력한다.
난이도

보통10점 중 5점

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

문제

협동 게임에서 배트(원반)의 움직임을 프로그래밍한다. 여러 명의 플레이어가 각자 1000×10001000 \times 1000 판 위의 포인터 하나를 조종한다. 각 포인터는 탄성 줄로 배트 중심에 연결되어 있으며, 줄이 배트를 잡아당겨 모든 힘이 균형을 이루는 평형 위치에서 배트가 멈춘다. 포인터들의 위치가 주어질 때 배트가 멈추는 위치를 구하여라.

포인터가 가하는 힘은 배트 중심까지의 거리에 비례하며, 방향은 포인터 쪽을 향한다. 다만 탄성 줄에는 100100 단위라는 최소 길이가 있어서, 배트 중심에서 100100 단위보다 가까운 포인터는 아무런 힘도 가하지 않는다.

평형 상태에서는 알짜힘이 00이므로, 배트는 자신으로부터 100100 단위 이상 떨어진 포인터들만의 평균(무게중심)에 놓인다. 어떤 포인터가 힘을 가하는지는 최종 위치에 따라 정해지고, 그 위치는 다시 어떤 포인터가 힘을 가하는지에 따라 정해지므로, 둘은 서로 일관되어야 한다.

100100 단위 경계에 아주 가깝게 멈추는 포인터는 없다고 가정해도 좋다. 따라서 힘을 가하는 포인터의 집합은 항상 명확하게 정해진다.

예를 들어 포인터가 (300,400)(300, 400), (600,300)(600, 300), (600,500)(600, 500)에 있으면 배트는 (500,400)(500, 400)에서 멈춘다. 네 번째 포인터를 (550,400)(550, 400)에 놓으면 이 점은 그 위치에서 100100 단위 이내에 있으므로 힘을 가하지 않아, 평형 위치는 그대로 (500,400)(500, 400)이다. (그림의 점선 원이 100100 단위 경계를 나타낸다.)

입력

입력은 여러 개의 게임 상황으로 이루어진다. 각 상황은 포인터의 개수를 나타내는 정수 nn (0≤n≤300 \le n \le 30)이 담긴 한 줄로 시작한다. 이어지는 nn개의 줄에는 각각 포인터 하나의 좌표 xx와 yy (0≤x,y≤10000 \le x, y \le 1000)가 공백으로 구분되어 두 정수로 주어진다. 입력은 n=0n = 0인 상황으로 끝나며, 그 상황은 처리하지 않는다.

출력

각 게임 상황마다 배트 중심의 평형 위치를 (x,y) 형식으로 한 줄에 출력한다. 두 좌표는 모두 가장 가까운 정수로 반올림한다.

예제3

  1. 예제 1

    입력
    4
    300 400
    600 300
    600 500
    550 400
    0
    
    예상 출력
    (500,400)
    
  2. 예제 2

    입력
    2
    200 200
    800 800
    0
    
    예상 출력
    (500,500)
    
  3. 예제 3

    입력
    3
    0 0
    300 0
    0 300
    0
    
    예상 출력
    (100,100)