2회 문제풀이 13 / ABC 145 C - Average Length
ABC 145 C - Average Length
【문제 개요】
좌표 평면에 N개의 마을이 있습니다. 마을 i은 좌표 (xi, yi)에 위치해있습니다. 마을 i와 마을 j의 거리는 √((xi - xj)^2+(yi - yj)^2)이다.
마을들을 전부 1번씩 방문하기 위해, 마을을 도달하기 위한 경로는 전부 N!개 입니다.
1번째로 갈 마을에서 출발해서 2번째로 갈 마을, 3번째로 갈 마을, …, N번째로 갈 마을로 도착할 때 까지의 이동거리를 그 경로의 길이로 합니다.
이러한 N! 경로의 길이의 평균치를 계산해주세요.
힌트 : 이진 탐색 알고리즘
【전제】
- 2 ≦ N ≦ 8
- -1000 ≦ xi, yi ≦ 1000
- (xi, yi) ≠ (xj, yj) (i ≠ j일때)
- 입력받을 모든 수는 정수이다.
【입력 형태】
1
2
3
4
N
x1 y1
...
xN yN
【출력 형태】
경로 길이의 평균값을 출력하라. 출력은 절대 오차 혹은 상대 오차가 10^(-6)이하인 경우 정답으로 판정된다.
【예시】
입력 예 1
1
2
3
4
3
0 0
1 0
0 1
출력 예 1
1
2.2761423749
마을을 방문하는 경로는 1→2→3, 1→3→2, 2→1→3, 2→3→1, 3→1→2, 3→2→1의 6종류입니다. 이중 경로 1→2→3의 길이는 √((0-1)^2 + (0-0)^2) + √((1-0)^2 + (0-1)^2) = 1+√2입니다. 마찬가지로 다른 경로에 대해서도 길이를 계산하면 경로 길이의 평균값은 ((1+√2)+(1+√2)+(2)+(1+√2)+(2)+(1+√2))/6 = 2.276142…입니다.
입력 예 2
1
2
3
2
-879981
-866890
출력 예 2
1
91.9238815543
마을을 방문하는 경로는 1→2, 2→1의 2종류밖에 없고, 둘은 동일한 경로이다.
입력 예 3
1
2
3
4
5
6
7
8
8
-406
10512859494362
-955
-475128553
-986
-885763
77449310
출력 예 3
1
7641.9817824387
ABC 145 C - Average Length
【문제 개요】
좌표 평면에 N개의 마을이 있습니다. 마을 i은 좌표 (xi, yi)에 위치해있습니다. 마을 i와 마을 j의 거리는 √((xi - xj)^2+(yi - yj)^2)이다.
마을들을 전부 1번씩 방문하기 위해, 마을을 도달하기 위한 경로는 전부 N!개 입니다.
1번째로 갈 마을에서 출발해서 2번째로 갈 마을, 3번째로 갈 마을, …, N번째로 갈 마을로 도착할 때 까지의 이동거리를 그 경로의 길이로 합니다.
이러한 N! 경로의 길이의 평균치를 계산해주세요.
힌트 : 이진 탐색 알고리즘
【전제】
- 2 ≦ N ≦ 8
- -1000 ≦ xi, yi ≦ 1000
- (xi, yi) ≠ (xj, yj) (i ≠ j일때)
- 입력받을 모든 수는 정수이다.
【입력 형태】
1
2
3
4
N
x1 y1
...
xN yN
【출력 형태】
경로 길이의 평균값을 출력하라. 출력은 절대 오차 혹은 상대 오차가 10^(-6)이하인 경우 정답으로 판정된다.
【예시】
입력 예 1
1
2
3
4
3
0 0
1 0
0 1
출력 예 1
1
2.2761423749
마을을 방문하는 경로는 1→2→3, 1→3→2, 2→1→3, 2→3→1, 3→1→2, 3→2→1의 6종류입니다. 이중 경로 1→2→3의 길이는 √((0-1)^2 + (0-0)^2) + √((1-0)^2 + (0-1)^2) = 1+√2입니다. 마찬가지로 다른 경로에 대해서도 길이를 계산하면 경로 길이의 평균값은 ((1+√2)+(1+√2)+(2)+(1+√2)+(2)+(1+√2))/6 = 2.276142…입니다.
입력 예 2
1
2
3
2
-879981
-866890
출력 예 2
1
91.9238815543
마을을 방문하는 경로는 1→2, 2→1의 2종류밖에 없고, 둘은 동일한 경로이다.
입력 예 3
1
2
3
4
5
6
7
8
8
-406
10512859494362
-955
-475128553
-986
-885763
77449310
출력 예 3
1
7641.9817824387