e-olymp
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 k-cı təpəsindəki üzlərinin sayını hesablayasınız.

Giriş verilənləri

Girişin birinci sətrində T (1T100) testlərin sayı yerləşir. Hər bir testin birinci sətrində çoxluqdakı nöqtələrin N (4N30) sayı yerləşir. Daha sonra hər birində 3 ədəd-həmin nöqtələrin X, Y, Z (–1000X, Y, Z1000) koordinatları olan 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.

Çıxış verilənləri:

T sayda testin hər biri üçün “Case #A: ” şəklində sətir verin. Burada A testin nömrəsidir(1-dən başlayaraq), sonra isə əlavə M sayda sətir verin. Burada 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 M sətrin hər birində iki ədəd verilir: k- üzdəki tillərin sayı və qk – çoxüzlüdəki 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 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
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
Case #1:
3: 5
5: 1
Case #2:
3: 4