Masala #0970

Xotira 16 MB Vaqt 1250 ms
14

Uchburchaklar yasash

Yangi yilda arafasida eng ko`p tilga olinadigan geometrik figura - yulduz bo`lsa kerak. Chunki archaning uchida ham yulduz turadi, qor parchasini ham yulduzga o`xshatamiz va h.k. Ammo hozir Asilbek uchburchaklarga oid masala ishlamoqda.

Sizga dekart koordinatalar sistemasida \(K\) ta nuqta beriladi. Siz bu nuqtalardan \(N(3N \leq K)\)  ta uchburchak yasashingiz kerak. Bunda:

  • bitta nuqta ko`pi bilan bitta uchburchak yasashda qatnashishi mumkin;
  • yuzasi 0 ga teng uchburchak yasash taqiqlanadi;
  • hosil qilingan uchburchaklar yuzalari yig`inidisi minimal bo`lsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(K,N(1 \leq N \leq 6, 3N \leq K \leq 20)\) kiritiladi.

Keyingi \(K\) ta qatorning har birida ikkitadan butun son - \(X,Y(-100 \leq X,Y\leq 100)\) navbatdagi nuqtaning koordinatalari kiritiladi.


Chiquvchi ma'lumotlar:

Birinchi qatorda bitta son, hosil qilingan \(N\) ta uchburchaklar yuzasi yig`inidisini chiqaring.

Keyingi \(N\) ta qatorning har birida uchburchak hosil qilgan uchlik nuqtalarning tartib raqamlarini chiqaring. To`g`ri javob bir nechta bo`lsa istalganini chiqaring. Uchburchaklarni va nuqtalarning tartib raqamlarini ham istalgan tartibda chiqarishingiz mumkin.

Agar shartlarni qanoatlantiruvchi \(N\) ta uchburchakni yasashning iloji bo`lmasa, yagona qatorda "IMPOSSIBLE" deb chiqaring.


Misollar
# input.txt output.txt
1
4 1
0 0
4 0
0 3
0 10
6
1 2 3
2
5 1
-1 -1
3 3
-2 -2
4 4
0 0
IMPOSSIBLE
3
5 1
-1 -1
3 3
-2 -2
4 4
-2 1
1.5
3 5 1