#445 yet another mst problem

Loading problem...

Preparing the statement, recent submissions, and submit form.

#445 yet another mst problem | DOJ

Statement

좌표평면 위에 서로 다른 $N$ 개의 정수점이 주어진다. 두 점 $(x_1,y_1)$ 과 $(x_2,y_2)$ 사이의 거리는 맨해튼 거리 $|x_1-x_2|+|y_1-y_2|$ 이다.

주어진 점 가운데 정확히 하나를 골라 원하는 정수점으로 옮길 수 있다. 옮긴 뒤의 $N$ 개 점을 정점으로 하는 최소 스패닝 트리의 가중치 합을 가능한 한 작게 만들려고 한다.

가능한 최소 가중치 합을 구하여라. 고른 점을 원래 위치로 옮기거나 다른 점과 같은 좌표로 옮겨도 된다.

입력은 다음과 같은 형식으로 주어진다.

$T$ case $_1$ case $_2$ $\vdots$ case $_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_N\ y_N$

각 테스트 케이스마다 가능한 최소 맨해튼 MST 가중치 합을 한 줄에 출력한다.

#	Score	Constraints
1	25	$N \leq 8$ . 모든 테스트 케이스에 대한 $N$ 의 합은 $8$ 이하이다.
2	75	추가적인 제약이 없다.

Input

Output

$(2,2)$ 의 점을 $(2,1)$ 로 옮기면 가중치가 각각 $1$ 인 두 간선으로 스패닝 트리를 만들 수 있다.