문제 링크
문제 요약
n개의 국가가 주어지며, 각 국가는 2차원 평면상의 좌표로 표현됩니다.
이 국가들은 원형으로 연결되어 있으며, 각 국가는 바로 옆의 두 이웃 국가와 외교 관계를 맺습니다.
외교 관계를 맺은 두 국가 간의 양자 회담 장소를 정해야 하는데, 이 장소는 두 국가의 외교관이 이동하는 거리가 같도록 해야 하며, 이동 거리는 최소화되어야 합니다.
(이는 결국 두 국가의 좌표를 잇는 선분의 중점으로 정해집니다.)
풀이
문제에서 요구하는 회담 장소의 조건은 “두 외교관이 이동하는 거리가 같도록 하면서 이동 거리는 최소화”하는 것입니다. 이는 기하학적으로 두 점을 잇는 선분의 중점을 의미합니다. 따라서, 인접한 두 국가의 좌표가 주어졌을 때, 해당 두 좌표의 중점을 계산하는 것이 핵심입니다.
주어진 n개의 국가 좌표를 라고 할 때, 각 회담 장소는 다음과 같이 계산됩니다:
- 와 의 중점
- 와 의 중점 … n. 와 의 중점 (원형 연결이므로 마지막 국가와 첫 번째 국가가 이웃)
각 중점 는 두 점 과 에 대해 다음과 같이 계산됩니다:
주의
- 입력은 EOF (End Of File)로 종료되므로,
try-except EOFError구문 등을 사용하여 입력을 잘 처리해야 합니다.
정답 코드
def solve():
while 1:
try:
n, *l = map(int, input().split())
except EOFError:
break
axis = [(l[i], l[i+1]) for i in range(0, len(l), 2)]
ans = []
for i in range(n):
fi = axis[i]
se = axis[(i + 1) % n] # 다음 국가 (n번째 국가 다음은 0번째 국가)
ans.append((fi[0] + se[0]) / 2) # X좌표 중점
ans.append((fi[1] + se[1]) / 2) # Y좌표 중점
print(n, end=" ")
for i in ans:
print(f"{i:.6f}", end=" ") # 소수점 이하 6자리까지 출력
print()
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()