25554번 - 포닉스의 신비한 분자 보고서 스페셜 저지

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$인 순서임을 의미한다.