SOLINFO.ro Runda 3 | Pădurar

Un pădurar tocmai a fost pus ca șef la o nouă pădure. El vede că pădurea lui are destui de puțini copaci, așadar el decide să planteze niște copaci noi. În loc să primească oferte simple, în care să primească un număr de copaci pentru o sumă de bani, el primește ca oferte drepte de copaci, pentru suma incredibilă de 0,00 lei! Observând această posibilitate, el vrea să aleagă $K$ din aceste drepte, astfel încât aria poligonului obținut din câteva puncte de intersecție a acestor drepte să fie cât mai mare! Un poligon cu o arie cât mai mare îi permite pădurarului să aducă cât mai multe animale și câți mai mulți turiști, deci poate să transforme pădurea într-o afacere! Pădurarul nostru e doar interesat de arie, nu și de dreptele pe care le alege. Fiind cam leneș, vă oferă ca recompensă 100 de puncte dacă îl ajutați să rezolve problema!

Cerință

Ajutați-l pe pădurar să transforme pădurea într-o afacere, precizând aria maximă a unui poligon obținut din selectarea a câteva puncte de intersecție a $K$ drepte.

Date de intrare

Pe prima linie se vor afla numerele $N$ și $K$, care reprezintă numărul de drepte și numărul de drepte pe care avem voie să le selectăm. Pe următoarele $N$ linii se vor afla $3$ numere: $a$, $b$, $c$, care reprezintă ecuația dreptei (ecuația unei drepte va fi de forma $ax + by + c = 0$)

Date de ieșire

Se va afișa aria maximă a unui poligon format din câteva vârfuri ale intersecțiilor celor $K$ drepte selectate.
Puteți afișa numărul cu câte zecimale doriți. Răspunsul va fi considerat corect dacă diferența în modul între valoarea afișată și răspunsul comisiei este de cel mult $10^{-5}$.

Restricții și precizări

• $3 \leq K \leq N \leq 14$
• $-10^{6} \leq a, b, c \leq 10^{6}$
• Se garantează că toate numerele din input sunt numere întregi
• Se garantează că pantele dreptelor sunt distincte
• Prin câteva puncte selectate ne referim la un număr mai mare sau egal cu $3$ si cel mult egal cu $\frac{K \cdot (K - 1)}{2}$
• Pentru $10$ puncte, $N = 3$ (testul 3)
• Dacă diferența dintre răspunsul dat de program și cel al comisiei este cel mult $10^{-3}$, atunci se va acorda 70% din punctaj
• Dacă diferența dintre răspunsul dat de program și cel al comisiei este cel mult $10^{-1}$, atunci se va acorda 20% din punctaj

Exemplu

stdin

4 3
1 0 0
0 1 0
1 -1 1
-1 -1 -2

stdout

2.25

Explicație

Folosim dreptele 1, 3 și 4. Poligonul de arie maximă este format din următoarele 3 puncte: intersecția dreptelor 1 și 3, intersecția dreptelor 3 și 4, intersecția dreptelor 4 și 1.