eolymp
bolt
Try our new interface for solving problems
Məsələlər

Çoxüzlü

Çoxüzlü

Üçölçülü fəzada nöqtələr çoxluğu verilmişdir. Sizin tapşırıq ondan ibarətdir ki, bütün verilən nöqtələri özündə saxlayan ən az həcmə malik qabarıq çoxüzlünün \textbf{k}-cı təpəsindəki üzlərinin sayını hesablayasınız. \InputFile Girişin birinci sətrində \textbf{T} (\textbf{1} ≤ \textbf{T} ≤\textbf{100}) testlərin sayı yerləşir. Hər bir testin birinci sətrində çoxluqdakı nöqtələrin \textbf{N} (\textbf{4} ≤ \textbf{N} ≤ \textbf{30}) sayı yerləşir. Daha sonra hər birində \textbf{3} ədəd-həmin nöqtələrin\textbf{ X}, \textbf{Y}, \textbf{Z} (\textbf{--1000} ≤ \textbf{X}, \textbf{Y}, \textbf{Z} ≤ \textbf{1000}) koordinatları olan \textbf{N} sətir gəlir. Bəzi nöqtələrin koordinatları eyni ola bilər! Zəmanət verilir ki, bütün nöqtələrin yerləşdiyi istənilən qabarıq çoxüzlü müsbət həcmə malikdir. \OutputFile \textbf{T} sayda testin hər biri üçün “\textbf{Case #A}: ” şəklində sətir verin. Burada \textbf{A} testin nömrəsidir(\textbf{1}-dən başlayaraq), sonra isə əlavə \textbf{M} sayda sətir verin. Burada \textbf{M} müxtəlif tipli üzlərin sayıdır( üzlərin tipi dedikdə onun tillərinin sayı başa düşülür). Sonrakı ardıcıl \textbf{M} sətrin hər birində iki ədəd verilir:\textbf{ k}- üzdəki tillərin sayı və\textbf{ q_k} -- çoxüzlüdəki \textbf{k} tilli üzlərin sayı. k-dan sonra ":"iki nöqtə çap edilir və sonra boşluq işarəsi qoyulur. Nəticələri\textbf{ k}-nın artma sırası ilə vermək lazımdır. Üzdəki tillərin sayı yalnız həndəsi təsəvvürlərlə müəyyənləşir. Başqa sözlə, əgər nöqtə üzün tərəfi üzərində yerləşirsə, o til hesaba alınmır, yox əgər bir neçə nöqtə bir til üzərində yerləşirsə, onda onları bir til hesab etmək lazımdır.
Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
2
6
0 0 0
2 0 0
0 2 0
2 2 0
3 1 0
1 1 1
5
0 0 0
1 1 0
0 2 0
2 1 0
1 1 1
Çıxış verilənləri #1
Case #1:
3: 5
5: 1
Case #2:
3: 4