포닉스의 신비한 분자 보고서

POSTECH의 비밀 연구실에서 최근 신비한 기체 분자가 발견되었다.

신비한 기체 분자는 2차원 평면 위에 단순 다각형의 형태로 존재한다.

신비한 기체 분자는 모두 하나의 큰 통에 담겨 관리되며, 통 안의 분자끼리는 서로 반응하지 않는다. 한 종류 분자의 부분 압력은 그 종류 분자의 수에 비례하고, 모든 종류의 부분 압력을 합하면 전체 압력과 같다.

즉, 전체 압력이 $P$, 분자 수가 모두 $N$개, 특정 종류의 분자가 $n$개라면 이 종류의 부분 압력은 $P \times \frac{n}{N}$이 된다.

이 연구실의 대학원생 포닉스는 큰 통에 담긴 여러 종류의 신비한 기체 분자를 분류하여 보고서를 작성해야 한다.

분자의 특성은 모양에 의해서만 정해진다. 평행이동과 회전이동으로 서로 겹쳐질 수 있다면 같은 종류의 분자이고, 그렇지 않다면 다른 종류의 분자이다. 대칭이거나 닮은 관계인 두 분자라도 평행이동과 회전이동만으로 겹쳐지지 않는다면 서로 다른 종류로 취급한다.

$N$개의 단순 다각형 모양 분자와 전체 압력 $P$가 주어질 때, 같은 종류끼리 묶어 종류의 수를 세고 각 종류의 부분 압력을 오름차순으로 출력하라.

첫째 줄에 신비한 기체 분자의 수 $N$이 주어진다. $(1 \leq N \leq 3\,000)$

둘째 줄에 전체 압력 $P$가 주어진다. $P$는 소수점 아래 둘째 자리까지 주어지며, $10^{-2} \leq P \leq 10^2$를 만족한다.

이어서 $N$개 분자의 모양에 해당하는 다각형이 주어진다. 각 다각형의 첫째 줄에는 꼭짓점의 수 $M_i$가 주어지고, 이후 $M_i$개 줄에 꼭짓점의 좌표 $x_{i,j}, y_{i,j}$가 주어진다. $(M_i \geq 3, -10^8 \leq x_{i,j}, y_{i,j} \leq 10^8)$. 모든 $M_i$의 합은 $10\,000$ 이하이다.

꼭짓점의 좌표는 모두 정수이고, 각 다각형의 꼭짓점은 반시계 방향으로 주어진다. 분자의 모양은 항상 단순 다각형이며, 인접한 두 변이 한 직선 위에 놓이는 경우는 없다. 입력은 분자의 실제 위치가 아니라 모양만 나타내므로, 좌표평면에서 서로 다른 두 분자가 겹칠 수 있다. 다각형이 볼록일 필요는 없다.

첫째 줄에 신비한 기체 분자의 종류 수를 출력하라.

이어서 모든 종류의 부분 압력을 한 줄에 하나씩 오름차순으로 출력하라. 절대오차 또는 상대오차가 $10^{-9}$ 이하이면 정답으로 인정한다.

단순 다각형은 변들이 꼭짓점에서만 만나는 다각형이다.

단순 다각형인 $n$각형의 꼭짓점 $(x_1, y_1), (x_2, y_2), \cdots (x_n, y_n)$이 반시계 방향으로 주어진다는 것은 $\overline{(x_{i,j}, y_{i,j})(x_{i,j+1}, y_{i,j+1})} (1 \leq j < n)$이 변이고 $\overline{(x_{i,n}, y_{i,n})(x_{i,1}, y_{i,1})}$이 변이며, $(x_1 \times y_2 + x_2 \times y_3 + \cdots + x_n \times y_1) - (y_1 \times x_2 + y_2 \times x_3 + \cdots + y_n \times x_1) > 0$이 성립하는 순서라는 뜻이다.