수도관 파열 (개정판)

면접 대비

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

요약

작업반이 원점에서 출발해 최대 10개의 누수를 순서대로 방문할 때, 각 지점이 시작 시각까지 기다린다는 조건 아래 총 손실 물의 양을 최소로 만드는 방문 순서를 찾는다.

난이도: 보통10점 중 6점
유형: 완전 탐색, 그리디, 시뮬레이션, 기하
정답자: 아직 제출이 없습니다

문제

수도관이 파열되면 물이 크게 낭비되는 이유는 대개 수리에 시간이 걸리기 때문입니다. 그 시간의 상당 부분은 수리반이 파열 지점까지 이동하는 데 쓰입니다. 특히 여러 곳이 동시에 터졌는데 이를 한꺼번에 처리할 수리반이 부족할 때 문제가 됩니다. 이때는 물이 더 많이 새는 먼 지점을 먼저 갈지, 가까이 있어 빨리 처리할 수 있는 몇 곳을 먼저 고칠지 결정해야 합니다. 이는 자명하지 않은 최적화 문제이며, 바로 그 문제를 여기서 풀게 됩니다.

파열 지점의 목록이 주어집니다. 각 지점마다 좌표 $(x, y)$ , 물이 새기 시작하는 시각 $t$ , 그리고 물이 흐르는 속도(유량) $r$ 가 주어집니다. 수리반은 시각 $0$ 에 원점 $(0, 0)$ 에서 출발하며, 주어진 속도 $v$ 로 직선을 따라 이동합니다(도로나 장애물은 없습니다). 목표는 방문 순서를 정하여 손실되는 물의 총량을 최소로 만드는 것입니다.

한 파열 지점에서 손실되는 물의 양은 $r \times (\text{수리 시각} - t)$ 이며, 수리 시각은 수리반이 그 지점에 도착하는 시각입니다. 수리는 즉시 끝나고 곧바로 다음 지점으로 출발할 수 있습니다. 수리반은 모든 파열의 미래 정보를 알고 있지만, 어떤 지점이 시각 $3$ 에 터진다면 시각 $2.5$ 에 그곳에 도착해도 소용이 없습니다. 시각 $3$ 이 될 때까지 기다렸다가 수리해야 하며, 이 경우 그 지점의 손실은 $0$ 입니다.

입력

첫 줄에는 데이터 집합의 개수 $K$ 가 주어지고, 이어서 $K$ 개의 데이터 집합이 다음 형식으로 주어집니다.

각 데이터 집합의 첫 줄에는 파열 지점의 수를 나타내는 정수 $n$ ( $1 \le n \le 10$ ) 과 수리반 트럭의 속도를 나타내는 실수 $v > 0$ 이 주어집니다.

이어지는 $n$ 개의 줄에는 각각 하나의 파열 지점을 설명하는 네 실수 $x_i,\ y_i,\ t_i,\ r_i$ 가 주어집니다. $(x_i, y_i)$ 는 파열 지점의 좌표로 $-1000.0 \le x_i, y_i \le 1000.0$ 이고, $0 \le t_i \le 1000.0$ 은 그곳의 관이 터진 시각, $0 \le r_i \le 1000.0$ 은 물이 흐르는 속도입니다. 수리반이 파열 지점에 도착하면 즉시 수리가 끝나 곧바로 다음 지점으로 이동할 수 있다고 가정합니다.

출력

각 데이터 집합에 대해, 한 줄에 Data Set x: 를 출력합니다. 여기서 $x$ 는 그 데이터 집합의 번호이며 $1$ 부터 시작합니다.

다음 줄에는 수리반이 최적의 순서로 파열 지점들을 방문했을 때 손실되는 물의 최소 총량을 소수점 아래 둘째 자리까지 반올림하여 출력합니다. 수리반은 시각 $0$ 에 원점 $(0, 0)$ 에서 출발합니다.

연속한 데이터 집합 사이는 빈 줄 하나로 구분합니다.

예제6

예제 1

입력

2
1 2
6 0 0 1
5 1.0
3.2 0 0 10
-4 -3 6 1000
0 0 15 0.1
0 1 17 0.01
0 -2 17 0.015

예상 출력

Data Set 1:
3.00

Data Set 2:
138.27

예제 2
입력
```
1
1 1
3 4 0 2
```
예상 출력
```
Data Set 1:
10.00
```
예제 3
입력
```
1
1 10
1 0 100 5
```
예상 출력
```
Data Set 1:
0.00
```

예제 4

입력

예상 출력

Data Set 1:
111.05

예제 5

입력

예상 출력

Data Set 1:
0.00

예제 6

입력

1
2 1
5 0 0 10
5 0.01 100 1000

예상 출력

Data Set 1:
50.00