공기역학

빌은 비밀 연구소에서 일하며 공기역학 부서를 이끌고 미사일을 설계한다.

공기역학의 놀라운 결과 중 하나가 휘트컴 면적 법칙(Whitcomb area rule)이다. 높은 아음속으로 비행하는 물체는 국소적으로 초음속 기류를 만들고, 그로 인해 생기는 충격파가 조파 저항(wave drag)을 일으킨다. 조파 저항은 물체의 정확한 형태가 아니라 오직 단면적 분포에만 의존한다.

물체의 진행 방향을 가리키는 OZ 축을 갖는 좌표계를 생각하자. 평면 $z = z_0$으로 물체를 자른 단면의 넓이를 $S(z_0)$이라 하자. $z_0$을 $S(z_0)$으로 보내는 함수 $S$가 물체의 단면적 분포이다. 이상적인 공기역학 형상인 시어스-핵 물체(Sears-Haack body)가 있는데, 물체의 단면적 분포가 시어스-핵 물체의 분포에 가까울수록 조파 저항이 작아진다. 이것이 휘트컴 면적 법칙의 핵심이다.

빌의 부서는 미사일을 제작하기 전에 컴퓨터 시뮬레이션으로 공기역학 특성을 연구한다. 미사일의 단면적 분포를 근사하기 위해 $z_{min}$부터 $z_{max}$까지의 모든 정수 $z_0$에서 $S(z_0)$을 표본으로 구한다.

주어진 미사일에 대해 $z_{min}$부터 $z_{max}$까지(양 끝 포함)의 모든 정수 $z_0$에 대한 $S(z_0)$을 구하라. 미사일은 주어진 모든 점을 포함하는 최소 볼록 입체(볼록 껍질)이다. 주어진 점들 중 한 평면 위에 있지 않은 네 점이 존재함이 보장된다.

첫째 줄에 정수 $n$, $z_{min}$, $z_{max}$가 주어진다 ($4 \le n \le 100$, $0 \le z_{min} \le z_{max} \le 100$).

이어지는 $n$개의 줄에는 각각 한 점의 좌표 $x$, $y$, $z$가 정수로 주어진다. 모든 좌표의 절댓값은 $100$ 이하이다. 어떤 두 점도 일치하지 않으며, 한 평면 위에 있지 않은 네 점이 존재한다.

$z_{min}$부터 $z_{max}$까지(양 끝 포함)의 각 정수 $z_0$에 대해, $z_0$이 증가하는 순서로 단면의 넓이 $S(z_0)$을 한 줄에 하나씩 출력하라.

모든 단면은 볼록 다각형이며 그 꼭짓점은 입체의 모서리와 평면 $z = z_0$의 교점이므로 각 꼭짓점의 좌표는 유리수이고 $S(z_0)$은 항상 유리수이다. $S(z_0)$을 기약분수 p/q 형태로 출력하라. 여기서 $q \ge 1$이고 $\gcd(p, q) = 1$이다. 특히 넓이가 정수 $a$이면 a/1로, 넓이가 $0$이면(평면이 입체를 지나지 않거나 한 점 또는 선분에서만 닿는 경우) 0/1로 출력한다.