Programozás‎ > ‎Feladatok‎ > ‎

Háromszög

Egy háromszög alakú papírból szeretnénk papírdíszt készíteni. A háromszöget oldalaival párhuzamos egyenesek kisebb háromszögekre osztják, és csak ezek mentén tudunk pontosan vágni. Sajnos a papírból már kivágtak néhány kisebb háromszöget, ezért a megmaradt anyagból kell kivágni a lehetséges legnagyobbat.
 

Feladat

Írj programot, amely megadja a maximális területű kivágható háromszög méretét! A méretet a kisháromszögek számával kell megadni.

Bemenet

A haromszog.be szöveges állomány tartalmazza a teszteseteket.
Az első sor a papírháromszög oldalának hosszát tartalmazza (1 <= n <= 100). Utána a háromszög leírása következik n sorban. Minden sor háromféle karaktert tartalmazhat:
  • - jelzi a használható háromszögeket
  • # jelzi a már kivágott háromszögeket
  • szóközök formázzák a bemenetet háromszög alakúra
A bemenet több ilyen blokkot tartalmazhat, a bemenet végét egy "0" jelzi.

Kimenet

A haromszog.ki szöveges állományba soronként egy-egy számot, a megfelelő tesztesetben kivágható maximális háromszög területét kell írni. 

Példa

Bemenet  Kimenet
5
#-##----#
 -----#-
  ---#-
   -#-
    -
4
#-#-#--
 #---#
  ##-
   -
0
9
4


Tesztadatok

Címkék

A feladat forrása: ???
Algoritmusok: geometriai algoritmusok, háromszög rács, üres háromszög, dinamikus programozás

megoldás