Muzey
Фlatlandiya Federal Universitetində idman nailiyyətləri muzeyi açıldı. Muzeyin əsas qüruru, idman proqramlaşdırma yarışlarından müxtəlif suvenirlərin sərgiləndiyi zalıdır.
Proqramlaşdırma getdikcə daha populyarlaşır və bu zalın maraqlı ziyarətçilərinin sayı artır. Buna görə də muzeyin direktoru suvenirlərin təhlükəsizliyindən narahat olmağa başlayır. Əvvəlcə direktor, suvenirlərin yerləşdiyi bir və ya iki zonanı ziyarətçilərdən ayırmağa qərar verdi ki, onlar sərbəst dolaşa bilməsinlər və yalnız kənardan baxa bilsinlər.
Zal konveks çoxbucaqlı formasındadır və suvenirlər bu çoxbucaqlının içindəki nöqtələrdir. Direktor, zalın künclərində yerləşən zirvələrlə bir və ya iki üçbucaq seçmək istəyir ki, bu üçbucaqların ümumi daxili hissəsi olmasın (yəni kəsişmə sahəsi sıfır olsun) və hər bir suvenir üçbucaqlardan birinin içində olsun.
Direktor ziyarətçilərə mümkün qədər az narahatlıq vermək istəyir, buna görə də seçilmiş üçbucaqların ümumi sahəsi minimal olmalıdır, hər bir üçbucağın sahəsi isə mütləq müsbət olmalıdır. Direktora eksponatları qorumaqda kömək edin.
Giriş məlumatları
Birinci sətir testlərin sayı t-ni ehtiva edir. Sonra t blok gəlir, hər biri aşağıdakı kimi görünür.
Blokun birinci sətirində çoxbucaqlının zirvələrinin sayı n və zalda olan suvenirlərin sayı m verilir (3 ≤ n ≤ 2000, 1 ≤ m ≤ 2000).
Növbəti n sətirdə iki tam ədəd xh[i] və yh[i] - çoxbucaqlının zirvələrinin Dekart koordinat sistemindəki koordinatları verilir (-10^9 ≤ xh[i], yh[i] ≤ 10^9). Zirvələr saat əqrəbi istiqamətinin əksinə ardıcıllıqla verilir.
Növbəti m sətirdə iki tam ədəd xs[i], ys[i] - suvenirlərin koordinatları verilir (-10^9 ≤ xs[i], ys[i] ≤ 10^9).
Bütün suvenirlərin zalın içində olduğu və verilmiş n + m nöqtələrdən heç bir üçü bir düz xətt üzərində olmadığı təmin edilir.
Bütün test nümunələrində verilən məlumatların cəmi n və m hər biri 2000-i keçmir.
Çıxış məlumatları
Hər bir t test üçün aşağıdakıları çıxarın.
Əgər tələb olunan şəkildə bir və ya iki üçbucaq seçmək mümkün deyilsə, ayrı bir sətirdə -1 çıxarın.
Əks halda, birinci sətirdə seçilmiş üçbucaqların sayı k (1 ≤ k ≤ 2) və növbəti k sətirdə zalın zirvələrinin nömrələrini - üçbucağın zirvələri olan üç tam ədəd çıxarın.
Əgər bir neçə optimal cavab varsa, onlardan hər hansı birini çıxarın.
Diqqət yetirin ki, yalnız seçilmiş üçbucaqların ümumi sahəsini minimallaşdırmaq tələb olunur.
Qeyd
Şəkildə birinci və üçüncü test nümunələrində üçbucaqları seçməyin optimal yolları, həmçinin ikinci test nümunəsində suvenirlərin yerləşməsi göstərilmişdir, burada bir və ya iki üçbucaq seçmək mümkün deyil.
