창고 위치 계획

산업공학의 많은 부분은 산업 공정을 더 효율적으로 만들도록 계획하고 개선하는 일이며, 이 과정에서 제품 기획이나 공급 관리 등 다양한 최적화 문제를 풀게 된다. 이런 문제 중 상당수는 꽤 복잡하지만, 핵심 주제 하나를 자연스럽고 깔끔하게 단순화한 형태는 쉽게 이해할 수 있다.

창고 위치 계획 문제에서는 물품을 공급받아야 하는 여러 개의 상점이 있다. 이 상점들에 물품을 공급하기 위해 창고를 여러 개 지을 수 있다. 창고를 하나 짓는 데는 그 위치에 따라 결정되는 건설 비용이 든다. 한편, 어떤 상점이 배정된 창고에서 멀리 떨어져 있을수록 그 상점까지 물품을 운송하는 비용이 커진다. 따라서 창고의 위치는 건설 비용과 운송 비용 사이에서 균형을 맞추어야 하며, 목표는 전체 비용이 최소가 되도록 창고를 짓는 것이다.

창고와 상점의 위치가 주어지면 운송 비용은 두 지점 사이의 유클리드 거리와 정확히 같다고 가정한다. 또한 한 번 지은 창고는 임의로 많은 상점에 물품을 공급할 수 있다고 가정한다. 창고는 반드시 하나 이상 지어야 한다. 전체 비용은 지은 창고들의 건설 비용의 합에, 모든 상점에 대해 각 상점이 배정된 창고까지의 운송 비용을 더한 값이다.

첫째 줄에는 데이터 집합의 개수를 나타내는 정수 $K \ge 1$이 주어진다. 각 데이터 집합의 형식은 다음과 같다.

• 데이터 집합의 첫째 줄에는 두 정수 $n$과 $m$이 주어진다. $n$은 상점의 수, $m$은 고려 대상인 창고 후보 위치의 수이다. 상점의 수는 $1 \le n \le 100$, 창고 후보 위치의 수는 $1 \le m \le 20$을 만족한다.
• 이어지는 $n$개의 줄에는 각 상점의 $x$, $y$ 좌표(실수)가 하나씩 주어진다.
• 그다음 $m$개의 줄에는 각 창고 후보 위치와 건설 비용이 실수 $x$, $y$, $p$로 주어진다. 여기서 $p \ge 0$이다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이며 $1$부터 시작한다. 그다음 줄에 모든 상점에 물품을 공급할 수 있는 최소 전체 비용을 소수점 둘째 자리까지 반올림하여 출력한다.