㈜ASD는 세계적인 쿼드콥터 제조업체이다. 이 회사는 최근 새로운 쿼드콥터 생산을 위한 새 공장을 짓기로 결정했다. 하지만, 아직 공장을 어디에 지을지는 정해지지 않았다.
매장은 생산된 쿼드콥터를 매장에 배송하는데 드는 비용을 최소화할 수 있는 위치에 세워야 한다. 새로운 쿼드콥터 판매를 하려는 매장은 $n$ 곳이 있다. 생산된 쿼드콥터는 각각 공장에서 매장으로 직선으로 비행하여 매장으로 배달된다. 공장과 어떤 상점 사이의 유클리드 거리가 $x$라면, 월 배송 비용은 $x$ 비트코인이 된다.
공장은 어디에나 지을 수 있으며, 어떤 지점에 상점이 있더라도 공장을 지을 수 있다(이 경우 배송 비용은 무료다).
상점의 좌표가 주어지면 공장을 건설할 최적의 장소를 찾으세요.
입력
입력의 첫 번째 줄에는 테스트 케이스 수가 주어진다. $z$ ($1 \leq z \leq 10$).
각 테스트 케이스의 첫 번째 줄에는 쿼드콥터를 판매하려는 상점의 수가 주어진다. $n$ ($2 \leq n \leq 1000$).
각 테스트 케이스에서 다음 $n$개의 줄에는 상점의 좌표를 나타내는 두 개의 정수가 주어진다. $x, y$ ($10^6 \leq x, y \leq 10^6$)
서로 다른 두 개의 상점은 같은 위치에 존재하지 않는다.
출력
각 테스트 케이스에 대해 매장까지의 거리 합을 최소화하는 점의 좌표를 출력한다. 답이 여러개라면 그 중 하나를 출력한다.
만약 실제 최적해 비용이 $x$이고 출력한 정답의 비용이 $y$일 경우, 다음의 조건에 한하여 정답으로 인정한다. $|\frac{y-x}{x}| < 10^{-6}$.
mango_clark 1년 전
문제
㈜ASD는 세계적인 쿼드콥터 제조업체이다. 이 회사는 최근 새로운 쿼드콥터 생산을 위한 새 공장을 짓기로 결정했다. 하지만, 아직 공장을 어디에 지을지는 정해지지 않았다.
매장은 생산된 쿼드콥터를 매장에 배송하는데 드는 비용을 최소화할 수 있는 위치에 세워야 한다. 새로운 쿼드콥터 판매를 하려는 매장은 $n$ 곳이 있다. 생산된 쿼드콥터는 각각 공장에서 매장으로 직선으로 비행하여 매장으로 배달된다. 공장과 어떤 상점 사이의 유클리드 거리가 $x$라면, 월 배송 비용은 $x$ 비트코인이 된다.
공장은 어디에나 지을 수 있으며, 어떤 지점에 상점이 있더라도 공장을 지을 수 있다(이 경우 배송 비용은 무료다).
상점의 좌표가 주어지면 공장을 건설할 최적의 장소를 찾으세요.
입력
입력의 첫 번째 줄에는 테스트 케이스 수가 주어진다. $z$ ($1 \leq z \leq 10$).
각 테스트 케이스의 첫 번째 줄에는 쿼드콥터를 판매하려는 상점의 수가 주어진다. $n$ ($2 \leq n \leq 1000$).
각 테스트 케이스에서 다음 $n$개의 줄에는 상점의 좌표를 나타내는 두 개의 정수가 주어진다. $x, y$ ($10^6 \leq x, y \leq 10^6$)
출력
각 테스트 케이스에 대해 매장까지의 거리 합을 최소화하는 점의 좌표를 출력한다.
답이 여러개라면 그 중 하나를 출력한다.
만약 실제 최적해 비용이 $x$이고 출력한 정답의 비용이 $y$일 경우, 다음의 조건에 한하여 정답으로 인정한다. $|\frac{y-x}{x}| < 10^{-6}$.