시간 제한메모리 제한제출정답맞은 사람정답 비율
4 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)53211636.364%

문제

군집화(clustering) 알고리즘은 같은 클러스터에는 최대한 비슷한 데이터가 묶이고, 서로 다른 클러스터 사이에는 다른 데이터들이 위치하도록 하는 알고리즘이다. UCP-Clustering은 군집화 알고리즘 중 하나로, 2차원 평면 위에 $n$개의 데이터가 주어질 때 다음과 같은 방식으로 데이터를 $k$개의 클러스터로 나눈다.

  1. 각 클러스터는 구심점이 되는 중심 좌표를 하나씩 가진다. $n$개의 데이터 중 서로 다른 $k$개를 무작위로 선택하고, 각 데이터의 좌표를 중심 좌표로 갖는 $k$개의 빈 클러스터를 만든다.
  2. 아래의 과정을 반복한다.
    1. 각각의 데이터에 대하여 유클리드 거리가 가장 가까운 클러스터의 중심 좌표를 선택하고, 그에 해당하는 클러스터에 그 데이터를 포함시킨다. 가장 가까운 중심 좌표가 여러 개라면 그중에서 가장 작은 것을 선택한다. 좌표 $(x_1, y_1)$이 $(x_2, y_2)$보다 작다는 것은 $x_1 < x_2$거나, $x_1=x_2$이고 $y_1<y_2$인 경우를 의미한다.
    2. 각각의 클러스터에 대하여 클러스터의 새로운 중심 좌표를 계산한다. 각 클러스터의 새로운 중심 좌표는 그 클러스터에 포함된 모든 데이터의 좌표들로부터 각 차원별로 중앙값을 계산하여 결정된다. 단, 값의 개수가 짝수일 경우, 중앙값은 값들을 정렬했을 때 가운데 두 값의 평균으로 계산된다.
    3. 만약 모든 클러스터의 새로운 중심 좌표가 원래의 중심 좌표와 같다면 알고리즘을 종료한다. 그렇지 않다면 클러스터 구성을 초기화하고, 이 새로운 중심 좌표들을 중심 좌표로 갖는 $k$개의 빈 클러스터를 새로 만든다.

예를 들어, 3개의 데이터 $\{(1, 2), (3, 4), (5, 6)\}$를 UCP-Clustering 알고리즘을 이용해 두 개의 클러스터로 나누는 상황을 생각해 보자. $(1, 2)$와 $(3, 4)$를 초기 중심 좌표로 선택하면 $\{(1, 2)\}$와 $\{(3, 4), (5, 6)\}$ 두 개의 클러스터로 나뉘고, 두 클러스터의 중심 좌표는 각각 $(1, 2)$, $(4, 5)$가 된다. 다른 예시로 $(1, 2)$와 $(5, 6)$을 초기 중심 좌표로 선택하면 $\{(1, 2), (3, 4)\}$와 $\{(5, 6)\}$으로 나뉘고, 두 클러스터의 중심 좌표는 각각 $(2, 3)$, $(5, 6)$이 된다. 예시에서 알 수 있듯이, 초기에 클러스터의 중심 좌표를 어떻게 선택하느냐에 따라 알고리즘의 실행 결과가 달라지며, 위의 두 경우에서는 2번 과정이 모두 2번 반복된다.

$k=2$로 고정한다면 가능한 초기 중심 좌표의 경우의 수는 총 $n(n-1)/2$ 가지이다. 알고리즘을 완료했을 때 두 클러스터의 중심 좌표로 가능한 경우를 모두 찾고, 각 경우에 대해 수렴하는 데까지 걸리는 2번 과정의 반복 횟수의 기댓값을 구하시오.

입력

첫 번째 줄에 데이터의 수 $N$이 주어진다. ($2 \leq N \leq 512$)

그 후 $N$개의 줄에 $i$번째 데이터의 좌표인 $(x_i, y_i)$가 공백을 사이에 두고 주어진다. 모든 좌표는 정수이며, 모든 데이터의 좌표는 서로 다르다. ($-10^6 \leq x_i, y_i \leq 10^6$)

출력

두 클러스터의 최종 중심 좌표 $\mu_1 = (x^{\mu}_{1}, y^{\mu}_{1})$, $\mu_2 = (x^{\mu}_{2}, y^{\mu}_{2})$와 클러스터의 중심 좌표가 두 좌표로 수렴하는 데까지 걸리는 2번 과정의 반복 횟수의 기댓값을 공백을 사이에 두고 출력한다. 단, 두 좌표 중 더 작은 쪽을 $\mu_1$으로 둔다. 가능한 좌표 쌍이 여러 개 존재하는 경우 $\mu_1$이 작은 것부터, $\mu_1$이 같은 경우는 $\mu_2$가 작은 것부터 출력한다. 출력하는 값의 절대 오차 또는 상대 오차는 $10^{-6}$까지 허용한다.

주어지는 모든 데이터에서 처음에 클러스터의 중심 좌표가 되는 데이터를 어떻게 고르더라도 UCP-Clustering이 실패하는 상황, 즉 두 클러스터의 중심 좌표가 같아지거나, 한쪽 클러스터가 비거나, 클러스터의 중심 좌표가 수렴하지 않게 되는 상황이 발생하지 않음이 보장된다.

예제 입력 1

3
1 2
3 4
5 6

예제 출력 1

1.0 2.0 4.0 5.0 2.000000
2.0 3.0 5.0 6.0 2.000000

예제 입력 2

4
0 0
0 3
3 0
3 3

예제 출력 2

0.0 0.0 3.0 3.0 1.000000
0.0 1.5 3.0 1.5 2.000000
0.0 3.0 3.0 0.0 1.000000
1.5 0.0 1.5 3.0 2.000000

노트

첫 번째 예제에서, 알고리즘은 다음과 같이 동작한다.

  • 초기 두 클러스터의 중심 좌표로 $(1, 2)$, $(3, 4)$를 선택한 경우: 첫 번째 반복을 통해 두 클러스터의 중심 좌표가 각각 $(1, 2)$, $(4, 5)$으로 바뀌고, 두 번째 반복에서 클러스터의 중심 좌표가 바뀌지 않아 알고리즘이 종료된다.
  • 초기 두 클러스터의 중심 좌표로 $(1, 2)$, $(5, 6)$를 선택한 경우: 첫 번째 반복을 통해 두 클러스터의 중심 좌표가 각각 $(2, 3)$, $(5, 6)$으로 바뀌고, 두 번째 반복에서 클러스터의 중심 좌표가 바뀌지 않아 알고리즘이 종료된다.
  • 초기 두 클러스터의 중심 좌표로 $(3, 4)$, $(5, 6)$를 선택한 경우: 첫 번째 반복을 통해 두 클러스터의 중심 좌표가 각각 $(2, 3)$, $(5, 6)$으로 바뀌고, 두 번째 반복에서 클러스터의 중심 좌표가 바뀌지 않아 알고리즘이 종료된다.

세 가지 경우를 모두 고려했을 때, 중심 좌표가 $\mu_1=(1, 2)$와 $\mu_2=(4, 5)$로 수렴하는 데에 걸리는 평균 반복 횟수는 2회이다. 마찬가지로, $\mu_1=(2, 3)$과 $\mu_2=(5, 6)$으로 수렴하는 데에 걸리는 평균 반복 횟수 또한 2회이다. 두 $\mu_1$ 중 $(1, 2)$가 $(2, 3)$보다 작으므로 $(1, 2)$와 $(4, 5)$로 수렴하는 경우부터 출력한다.