ACM 1998

Egy csúcstechnológiával dolgozó cég előállított egy új anyagot, amelyet mint szigetelőt szeretne piacra dobni. Az anyag négyzetes rácsszerkezetben növekvő kristály. A rácsszerkezet cellái 1 centiméterenként helyezkednek el. Minden cella pontosan 1 centiméter átmérőjűre nő.

Az anyag felhasználásához a kristályrács darabolása szükséges. A rács darabolása során jelentkező egyik probléma, hogy néhány cellába is belemetszünk. Ha egy cellát nem a közepénél vágunk el, elveszíti szigetelő tulajdonságát.
 
 

megmarad a szigetelőképesség	elvész a szigetelőképesség

A rácsszerkezet szigetelőképessége egyenesen arányos a sziegetelő tulajdonságú kristályok (vagy kristályrészek) teljes területével. A következő ábra egy sokszög alakú rácsrészt mutat, amelyen árnyékoltan láthatók a szigetelő kristályok.

A feladatod, hogy határozd meg a szigetelőképességet a szürkével jelzett terület kiszámításával.

Bemenet:

A bemeneti állomány tartalmazza a sokszög leírását. Minden leírás egy n pozitív egésszel kezdődik (3 <= n <= 25), megadja a csúcsok számát. A következő n egész számpár a csúcsok x és y koordinátáját adja meg. (A koordinátarendszert úgy helyeztük el, hogy a cellák középpontjai egész koordinátájúak legyenek.)

A csúcsok az óramutató járásának sorrendjében adottak. A sokszög konvex. A csúcspontok egyik koordinátája sem nagyobb abszolútértékű, mint 250. A bemeneteti állományt a 0 érték zárja.

Kimenet:

A kimenetbe tesztesetenként az eset sorszámát kell írni, a következő sorba a szigetelő tulajdonságú terület méretét kell írni 3 tizedesjegy pontossággal.

Példa:
 

INPUT.TXT	OUTPUT.TXT
5 0 2 3 5 6 3 6 0 1 0 0	Shape 1 Insulating area = 15.315 cm^2

Az alkimisták kísérletei, hogy ólomból aranyat csináljanak, évszázadokon át meghiúsult. Az utolsó Alkímista Klub Találkozón (Alchemist Club Meeting - ACM) szenzációs áttörés történt. Három vegyszer, az Algolene, Basicine és a Cobolase megfelelő arányú keverésével készített elegy az ólomból aranyat csinál. Azóta Algolene, Basicine és a Cobolase (röviden A, B, C) általában nem árulják egyenként , hanem csak a keverésükkel készített vegyület vásárolható meg.

Tekintsük a következő példát! Két vegyület kapható Algolene, Basicine és a Cobolase-ből, 1:2:3 és 3:7:1 keverési arányú. A vegyületek 1:2 arányú keverésével az A, B, C-ből álló keverék 7:16:5 arányú lesz. De nincs mód kombinálni a keverékeket, oly módon, hogy 3:4:5 arány legyen a végeredmény. Ha van egy 2:1:2 arányú keverékünk is, akkor a 3:4:5 keverési arány előállítható 8 rész 1:2:3, 1 rész 3:7:1 és 5 rész 2:1:2 arányú keverékből.

Határozd meg, hogy melyik keverék állítható elő a megadott arányú keverékekből, lehetőség szerint minimális mennyiségű alapanyagból. Írj programot, amely meghatározza a keverési arányokat!

Bemenet:

A bemeneti állomány néhány tesztesetet tartalmaz. Minden teszteset első sorában egy n egész szám van (0 <= n < 100), amely megadja, hogy hány keveréket használunk az adott esetben. A következő n sor három nemnegatív egészet (a_i, b_i, c_i) tartalmaz, amelyek az A, B, C vegyületek keverési arányát jelentik az i-ik vegyületnél. Legkevesebb egy összetevő pozitív minden vegyületnél.

Végül egy sorban három nemnegatív egész (a, b, c) található, amelyek megadják a vegyületek keverési arányát a készítendő vegyületben. Legalább egy szám pozitív.

Az input állomány a tesztesethez tartozó vegyületek számát mutató sorbeli nullával zárul.

Kimenet:

Minden tesztesetnél a "Mixture" szót kell kiírni, valamint a teszteset számát. A következő sorba a "Possible" illetve az "Impossible" szót kell írni, attól függően, hogy a kívánt vegyület kikeverhető-e vagy sem.

Példa:
 

INPUT.TXT	OUTPUT.TXT
2 1 2 3 3 7 1 3 4 5 3 1 2 3 3 7 1 2 1 2 3 4 5 0	Mixture 1 Impossible Mixture 2 Possible