UCP-Clustering

군집화(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, 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)$로 수렴하는 경우부터 출력한다.