NézetNyomtat

Konvex burok térben
Címkék > Feladat

Konvex burok térben

Egy ponthalmaz konvex, ha bármely két pontját összekötő szakasz is teljes egészében a halmazban van. Egy ponthalmaz konvex burka a legkisebb (legszűkebb) konvex halmaz, ami az eredeti ponthalmazt tartalmazza.
Példáu az $ X = {(0, 0, 0), (10, 0, 0), (0, 10, 0), (0, 0, 10)}$ halmaz konvex burka a felsorolt pontok által meghatározott tetraéder.
A feladatban csak olyan ponthalmazok szerepelnek, amelyeknek konvex burka csupa háromszöglappal rendelkező poliéder.

Feladat

Írj programot, ami megadja a konvex burok felszínét, egészre kerekítve.

Bemenet

A bemenet több tesztesetet tartalmaz, mindegyik eset első sora a pontok számát adja meg ($4 \le n \le 25$). Ezután $n$ sorban a pontok koordinátái következnek ($-100 \le x, y, z \le 100$). A bemenet végét egy 0 jelzi.

Kimenet

Minden kérdéshez írjuk ki a konvex burok felszínét, egészre kerekítve.

Példa

area.inarea.out
5 0 0 0 10 0 0 0 10 0 0 0 10 1 1 1 9 0 0 0 2 0 0 2 2 0 0 2 0 1 1 2 1 1 -2 1 1 -1 1 1 0 1 1 1 0 237 18

Tesztadatok