농구 골대 세우기

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

요약

주어진 가중치 좌표들에 대해 가중 맨해튼 거리의 합을 최소화하는 정수 좌표를 찾고, 동일하면 x가 작은 것, 그다음 y가 작은 것을 선택합니다.

문제

격자 나라에는 정수 좌표마다 마을이 있다. 어떤 두 마을 사이의 거리는 길을 따라 이동하는 최단거리, 즉 맨해튼 거리로 계산한다. 좌표 (x1, y1)에서 (x2, y2)까지의 거리는 |x2 - x1| + |y2 - y1|이다.

농구를 좋아하는 마을 n개의 위치와 각 마을의 사람 수가 주어진다. 나라에서는 모든 농구를 좋아하는 마을을 위해 농구 골대를 하나 세우려고 한다.

골대는 정수 좌표의 한 마을에 세워야 하며, 그 마을이 입력으로 주어진 마을일 필요는 없다. 각 농구를 좋아하는 마을에 대해 (그 마을에서 골대까지의 거리) × (그 마을의 사람 수)를 계산했을 때, 그 합이 최소가 되는 골대의 위치를 구하라.

첫 줄에 농구를 좋아하는 마을의 개수 n이 주어진다. 다음 n개의 줄에는 한 마을의 정보 xi yi pi가 주어진다. 이는 마을의 좌표가 (xi, yi)이고, 그 마을에서 농구를 좋아하는 사람 수가 pi명이라는 뜻이다.

두 마을의 위치가 같은 경우는 없다.

골대를 세울 마을의 좌표 x y를 한 줄에 출력한다. 답이 여러 개라면 x좌표가 가장 작은 위치를 고르고, 그래도 여러 개라면 y좌표가 가장 작은 위치를 고른다.