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

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