/**
 * TBD Genc Ankara Mayis 2010 Bulteni
 * Odullu Programlama Sorusu-3
 * C++ $ablonu
 * www.tbdgenc.com
 */

#include <iostream>
#include <string>
using namespace std;

/*
 * Uyari: Lutfen main ve yerlestir metodunun aciklamasini okuyunuz.
 */


struct Dikdortgen{
	/* 	Bu obje bu dosya icinde gorulebilir. Ek
		property'ler tanimlamak serbesttir.
	*/
	int x,y,genislik, yukseklik; // disaridan erisilebilir

	Dikdortgen(){
		x=0; y=0; genislik=0; yukseklik=0;
	}

	Dikdortgen(int Genislik, int Yukseklik){ // half ctor
		if(Genislik<0 || Yukseklik<0)
			cout<<("## UYARI: genislik veya yukseklik 0'dan kucuk olamaz!")<<endl;
		x = 0;
		y = 0;
		genislik = Genislik;
		yukseklik = Yukseklik;
	}

	Dikdortgen(int X, int Y, int Genislik, int Yukseklik){ // full ctor
		if(x<0 || y<0) cout<<("## UYARI: x veya y 0'dan kucuk olamaz!")<<endl;
		if(genislik<0 || yukseklik<0)
			cout<<("## UYARI: genislik veya yukseklik 0'dan kucuk olamaz!")<<endl;

		x = X;
		y = Y;
		genislik = Genislik;
		yukseklik = Yukseklik;
	}

	/**
	 * mevcut dikdortgenle digerinin kesisip kesismedigini tespit
	 * eder
	 * @param diger
	 * @return kesi$iyorlarsa true döner
	 * @author Sami Shaio (from java.awt.Rectangle), Ahmet Alp Balkan
	 * 	(modified)
	 */
	bool kesisiyorMu(Dikdortgen*& d){
		if (this->x == d->x && this->y == d->y &&
				this->yukseklik == d->yukseklik && this->genislik == d->genislik){
			return false; //dikdortgeni kendisiyle karsilastirmasini onleyelim
		} else {
			int tw, th, dw, dh;
			tw = this->genislik;
			th = this->yukseklik;
			dw = d->genislik;
			dh = d->yukseklik;

			if (dw <= 0 || dh <= 0 || tw <= 0 || th <= 0) {
				return false;
			}

			int tx, ty, dx, dy;
			tx = this->x;
			ty = this->y;
			dx = d->x;
			dy = d->y;

			tw += tx;
			th += ty;
			dw += dx;
			dh += dy;

			return ((dw < dx || dw > tx) &&
					(dh < dy || dh > ty) &&
					(tw < tx || tw > dx) &&
					(th < ty || th > dy));
		}
	}


	void print() {
		cout<<"[X="<<x<<", Y="<<y<<", W="<<genislik<<", H="<<yukseklik<<"]";
	}

	/**
	 * verilen bir noktanin dikdortgenin icinde veya ustunde
	 * kalip kalmadigini dondurur.
	 * @param X
	 * @param Y
	 * @return icindeyse true doner, degilse false
	 * @author Sami Shaio
	 */
	bool icindeMi(int X, int Y){
		int w = this->genislik;
		int h = this->yukseklik;

		if(w < 0 || h < 0) return false; // sifirdan kucuk boyut.

		if (X < x || Y < y) {
			return false;
		}
		w += x;
		h += y;
		return ((w < x || w > X) && (h < y || h > Y));
	}

	/**
	 * Verilen dikdortgenin baslangic (sol alt, guneybati)
	 * noktasini verilen koordinata tasir.
	 */
	void tasi(int X, int Y){
		if(X<0 || Y<0) cout<<("## UYARI: x veya y 0'dan kucuk olamaz! (tasirken)")<<endl;
		x = X;
		y = Y;
	}

}; // dikdortgen
/**
 * Verilen Dikdortgen listesinde o noktanin bir dikdortgenin icinde
 * kalip kalmadigini dondurur.
 *
 * @return bir dikdortgenin icinde kaliyorsa true doner,
 * 		   o nokta bossa false doner.
 */

void buradaDikdortgenVarMi(Dikdortgen**& liste, int sayi, int X, int Y){
	for(int i = 0; i < sayi; i++){
		if(liste[i]->icindeMi(X, Y)) {
			cout<<"(X="<<X<<", Y="<<Y<<")'deki: ";
			liste[i]->print();cout<<endl;
//			return true;
		}
	}
//	return false;
}

/**
 * Verilen Dikdortgen listesinde birbirleriyle kesisen dikdortgen
 * olup olmadigini dondurur.
 * @param liste
 * @return kesisen varsa true, yoksa (istenilen durum) false doner
 */
bool kesisenDikdortgenVarMi(Dikdortgen** & liste, int sayi){
	for(int i = 0; i < sayi; i++){
		for(int j = 0; j < sayi; j++){
			if(liste[i]->kesisiyorMu(liste[j])){
				cout<<("Kesi$en: "); liste[i]->print(); cout<<" ve "; liste[j]->print(); cout<<endl;
				return true;
			}
		}
	}
	return false;
}

int maximumX(Dikdortgen**& liste, int sayi){
	int max = 0; int tmp;

	for(int i = 0 ; i < sayi; i++){
		tmp = liste[i]->x + liste[i]->genislik;
		if (tmp>max) max = tmp;
	}

	return max;
}

int maximumY(Dikdortgen** &liste, int sayi){
	int max = 0; int tmp;

	for(int i = 0 ; i < sayi; i++){
		tmp = liste[i]->y + liste[i]->yukseklik;
		if (tmp>max) max = tmp;
	}

	return max;
}


void dikdortgenleriYazdir(Dikdortgen** liste, int sayi){
	for(int i = 0 ; i < sayi; i ++){
		(*liste[i]).print();
		cout<<endl;
	}
}


/**
 * Verilen Dikdortgen array'indeki dikdortgenleri
 * en verimli sekilde yerlestirir ve yeni array'i
 * dondurur.
 * """"BU KISIM KODLANACAKTIR""". EK METODLAR TANIMLANABiLiR.
 * SONRADAN TANIMLI METODLAR DA BURADAN CAGIRILABILIR.
 *
 * NOT: main tarafindan cagirilacak olan metod budur.
 * NOT: Dikdortgen.tasi metodu kullanilabilir.
 * NOT: C/C++'de array'ler referanslari ile gonderilmektedir.
 * 		Yapilan degisiklik orijinal array'deki nesneyi de
 * 		degistirir.
 *
 */
void yerlestir(Dikdortgen** & liste, int sayi){
	/*
	 * Yarismaci tarafindan kodlanacak.
	 */
	liste[1]->tasi(0,5);
	liste[2]->tasi(0,15);
}

/**
 * Lutfen algoritmanizi yerlestir metodu icine yaziniz.
 * Bu metodu sadece algoritmanizi farkli dikdortgenlerle
 * test etmek icin kullaniniz.
 */
int main() {
	int dikdortgenSayisi = 3; 			// x=0, y=0'da bazi dikdortgenler..
	Dikdortgen** liste = new Dikdortgen*[3];
	liste[0] = new Dikdortgen(5,5);
	liste[1] = new Dikdortgen(20,10);
	liste[2] = new Dikdortgen(10,20);



	cout<<("Baslangictaki Dikdortgenler:")<<endl;
	dikdortgenleriYazdir(liste, dikdortgenSayisi);


	cout<<endl; // bosluk
	cout<<"Kesi$en Dikdortgen?: "<<(kesisenDikdortgenVarMi(liste, dikdortgenSayisi)?"var":"yok")<<endl;

	/** BURADA METOD CAGIRILIYOR **/
	yerlestir(liste, dikdortgenSayisi); // "liste" degistirildi!
	/** BURADA METOD CAGIRILIYOR **/

	cout<<("\nBitisteki Dikdortgenler:")<<endl;
	dikdortgenleriYazdir(liste, dikdortgenSayisi);

	cout<<endl; // bosluk
	cout<<"Ta$ima Sonrasi Kesi$en Dikdortgen?: "<< (kesisenDikdortgenVarMi(liste, dikdortgenSayisi)?"var (yerlestir'DEN SONRA OLMAMASI GEREK!!!)":"yok (TAMAMDIR)")<<endl;

	cout<<endl; // bosluk
	int maxX = maximumX(liste, dikdortgenSayisi);
	int maxY = maximumY(liste, dikdortgenSayisi);

	cout<<"Maximum X koordinati: "<<maxX<<"\nMaximum Y koordinati: "<<maxY<<endl;
	cout<<"*** Maliyet = "<<(maxX+maxY)<<" TL. ***"<<endl; // buffer
}