Ultima inovatie in materie de microprocesoare este forma acestora: se produc microprocesoare în formă de triunghi dreptunghic isoscel. Microprocesoarele nu se fabrică individual. Există nişte plăci (denumite wafers) de formă dreptunghiulară de NxM cm. Pe aceste plăci este trasat un caroiaj (format din linii respectiv paralele cu laturile plăcii), caroiaj care împarte placa în NxM pătrate cu latura de 1 mm.
Un microprocesor poate fi plasat pe placă astfel încât cel puţin una dintre laturile sale să fie paralelă cu una dintre laturile plăcii, iar vârfurile triunghiului care reprezintă microprocesorul să fie plasat în punctele de intersecţie ale liniilor caroiajului. Evident, oricare două microprocesoare nu au voie să se suprapună.
În figurile 1, 2, 3 sunt reprezentate 3 variante greşite de a plasa microprocesoarele pe placă, iar în figurile 4 şi 5 sunt ilustrate două variante corecte:
Conducerea companiei a sesizat că există pierderi mari datorită faptului că spaţiul de pe placă nu este utilizat integral.
Cerinţă
Dată fiind configuraţia actuală a plăcii, să se determine numărul minim de microprocesoare ce trebuie să fie adăugate (în mod corect) pe placă astfel încât spaţiul de pe placă să fie complet utilizat.
Date de intrare
Fişierul de intrare placa.in conţine pe prima linie trei numere naturale N M K, reprezentând dimensiunile plăcii şi respectiv numărul de microprocesoare deja plasate pe placă. Pe următoarele K linii sunt descrise poziţiile microprocesoarelor existente pe placă. Pentru fiecare microprocesor sunt specificate pe o linie 6 numere întregi separate prin spaţii x1 y1 x2 y2 x3 y3, reprezentând în ordine abscisa şi ordonata punctelor în care se află fiecare dintre cele 3 vârfuri ale microprocesorului. Sistemul de coordonate utilizat are axele respectiv paralele cu laturile plăcii, colţul stânga jos fiind punctul de coordonate (0, 0), iar colţul dreapta-sus fiind punctul de coordonate (N, M).
Date de ieşire
Fişierul de ieşire placa.out va conţine pe prima linie un număr natural MIN reprezentând numărul minim de procesoare ce trebuie să fie adăugate pe placă astfel încât placa să fie complet utilizată. Pe următoarele MIN linii sunt descrise poziţiile celor MIN microprocesoare adăugate. Fiecare linie va conţine câte 6 numere întregi separate prin spaţii reprezentând în ordine abscisa şi ordonata punctelor în care se află fiecare dintre cele 3 vârfuri ale microprocesorului x1 y1 x2 y2 x3 y3.
