Depo

3 katlı villasından 1+1 stüdyo tipi eve taşınan ünlü futbolcu, eski eşyalarını depoya sığdırmaya çalışırken farkediyor ki bu hiç de küçümsenecek bir iş değil. Profesyonel yardım almak isteyen Alexander , tabiki size ulaşıyor.

Görev: Alexander'ın herbirisi yerden tavana kadar uzanan N tane dikdörtgen prizma şeklinde eşyası var. Bu eşyaların sığabileceği en küçük taban alanlı deponun alanını ve eşyaların yerleşim planını bulan program yazınız.

Açıklamalar:

• Eşyaları 90 derece döndürebilirsiniz ancak yan yatıramazsınız.
• Eşya sayısı N<=1000 ve eşya eni,boyu<=1000000(kuşbakışı görünümdeki en ve boy) olarak verilecektir.
• Bulduğunuz çözüm eğer geçerliyse, kullandığınız deponun alanı Y ise ve o girdi için bulunmuş en küçük alan X ise alacağınız puan şöyle hesaplanacaktır:
  P=(2-Y/X)*(girdinin_puan_değeri*3/4) +girdinin_puan_değeri*1/4 .
  P<0 ise 0 puan alacaksınız.

Geçerli bir çözümde olması gerekenler:

• Depo alanı dogru olmalı
• Çakışan esya bulunmamalı
• Tüm eşyalar yerleştirilmiş olmalı

Girdi(depo.gir):

N
a1 b1
a2 b2
...
aN bN (eşyaların kuş bakışı görünümlerindeki boyutları)

Çıktı(depo.cik):

X
x1 y1 z1
x2 y2 z2
...
xk yk zk
...
xN yN zN

X - (odanın toplam alanı)
(xk,yk) - k. eşyanın sol üst köşesinin koordinatları
zk - k. eşyanın döndürülüp dödürülmediği gösteren sayı
     k. eşya 90 derece döndürülmediyse zk=0
     k. eşya 90 derece döndürüldiyse zk=1

deponun sol üst köşesi (0,0) kabul edilecektir.