꿈을 꾸다...

/* 

Subject: #142 Mouse Clicks

e-mail: morcavon@gmail.com

Homepage: http://www.morcavon.com

Building: 27/04/2005 ~ 28/04/2005

Last Update: 28/04/2005

*/



/*

<CONDITION>

A mouse click in (or on the border of) a region selects that region,

otherwise it selects the closest visible ico(or icons int the case of a tie).

Later regions can be assumed to be in front of earlier regions.

Regions always overlap icons.

Origin (0, 0) is at the top left corner.

Icon # start from 1.

Label regions alphabetically in the order of arrival starting from 'A'.

No icon or region specifications will follow the first mouse click.



0 <= Coordinates(integer) <= 499

0 <= # of regions < 25

1 <= # of icons < 50



Type: I - Icon (followed x, y coordinates)

R - Region (x, y to x2, y2)

M - Mouse Click (follwed cursur coordinates)

-

<INPUT>

Type xCoord yCoord (x2Coord y2Coord)

...

#

-

<OUTPUT>

R

I

.....

*/





#include <iostream>

using namespace std;





struct Point

{

	short x, y;

};





struct Region {Point topLeft, bottomRight; struct Region *link; char flag;};

struct Icon {Point center; struct Icon *link; char flag;};

struct Mouse {Point clicked;};







template <typename T>

class List

{

private:

	T* list;





public:

	List() {list = NULL;}

	~List();



	void Add(T& r);

	void Remove(T* r);

	T* GetList() const {return list;}

};





template <typename T>

List<T>::~List()

{

	T *temp;

	for (T *w_ptr = list; w_ptr != NULL; w_ptr = temp) {

		temp = w_ptr->link;

		delete w_ptr;

	}

}



template <typename T>

void List<T>::Add(T& r)

{

	T *node = new T;

	*node = r;

	node->link = list; // 리스트가 거꾸로 만들어짐=_=

	list = node;

}



template <typename T>

void List<T>::Remove(T* r)

{

	if (list != NULL) {

		// 맨앞에 있는 노드를 삭제할 노드의 자리로 옮기는 방식으로 하면

		// 리스트를 유지하면서 노드를 삭제할 수 있다.

		T *ptemp = r->link;

		*r = *list;

		r->link = ptemp; // 복사하면서 사라진 링크 복구

		ptemp = list->link;

		delete list;

		list = ptemp;

	}

}













const Region* checkR(List<Region>& list, Mouse& click);

void checkI(List<Icon>& list, Mouse& click, int n);

int refresh(Region& r, List<Icon>& list);

int refresh(Icon& i, List<Region>& list);





int main()

{



	char type, flagR = 'A', flagI = '1';

	Region tempR;

	const Region *pRegion;

	Icon tempI;

	Mouse click;



	List<Region> regionList;

	List<Icon> iconList;



	while (cin >> type) {

		// R, I 입력시 마다 icon리스트를 재구성해서 region과 겹치는 아이콘은 없앤다.

		// 나중에 몰아서 하나 그때그때 하나 별 다를게 없을듯하다=_=

		if (type == 'R') {

			cin >> tempR.topLeft.x >> tempR.topLeft.y >> tempR.bottomRight.x >> tempR.bottomRight.y;

			tempR.flag = flagR++;

			regionList.Add(tempR);

			refresh(tempR, iconList);

		}

		else if (type == 'I') {

			cin >> tempI.center.x >> tempI.center.y;

			tempI.flag = flagI++;

			if (refresh(tempI, regionList)) // 기존 레젼에 포함되지 않으면 아이콘리스트에 추가

				iconList.Add(tempI);

		}

		else if (type == 'M') {

			cin >> click.clicked.x >> click.clicked.y;



			if ((pRegion = checkR(regionList, click)) != NULL) {

				// region 찾기

				cout << pRegion->flag << endl;

			}

			else {

				// icon 찾기

				checkI(iconList, click, flagI - '1');

			}

		}

		else if (type == '#')

			break;

	}



	return 0;

}







const Region* checkR(List<Region>& list, Mouse& click)

{

	// click을 포함하는 region을 찾아 리턴, 없으면 NULL리턴

	// 겹치는 region일 때는 나중에 입력된 것이 우선(그냥 리스트 순으로 검색하면 되는것임!으하하)



	for (const Region *w_ptr = list.GetList(); w_ptr != NULL; w_ptr = w_ptr->link) {

		if (click.clicked.x >= w_ptr->topLeft.x && click.clicked.x <= w_ptr->bottomRight.x

			&& click.clicked.y >= w_ptr->topLeft.y && click.clicked.y <= w_ptr->bottomRight.y)

			return w_ptr;

	}

	return NULL;

}





void checkI(List<Icon>& list, Mouse& click, int n)

{

	// list에서 click에 제일 근접한 아이콘들을 출력

	// n(아이콘의 총 개수(무시된 입력포함)) 만큼의 배열을 만들어 찾아낸 아이콘들의 포인터를 저장



	const Icon **result = new const Icon*[n];

	short i = 0;



	if ((result[i] = list.GetList()) == NULL)

		return;



	for (const Icon *w_ptr = result[i]->link; w_ptr != NULL; w_ptr = w_ptr->link) {

		v = ((2*click.clicked.x - w_ptr->center.x - result[i]->center.x) * 

			(result[i]->center.x - w_ptr->center.x)) +

			((2*click.clicked.y - w_ptr->center.y - result[i]->center.y) * 

			(result[i]->center.y - w_ptr->center.y));



		if (v == 0) {

			// 현재 선택된 최근접 아이콘과 같은 거리 떨어져있는 아이콘

			// 발견한 순서대로 포인터배열에 넣는다

			result[++i] = w_ptr;

		}

		else if (v < 0) {

			// w_ptr 아이콘이 더 가깝다, 현재 result에 설정된 아이콘을 변경한다

			i = 0;

			result[i] = w_ptr;

		}

	}





	///////////////////////////////////

	////////////// 출력 ///////////////

	///////////////////////////////////

	// result배열을 뒤에서 부터 거꾸로 출력(아이콘 번호순대로 나오게 됨)

	while (i >= 0) {

		cout.width(3);

		cout << (int)(result[i--]->flag - '0');

	}

	cout << '\n';

}





int refresh(Region& r, List<Icon>& list)

{

	// r과 겹치는 아이콘들을 찾아내 리스트에서 지움

	for (Icon *w_ptr = list.GetList(); w_ptr != NULL; w_ptr = w_ptr->link) {

		if (w_ptr->center.x >= r.topLeft.x && w_ptr->center.x <= r.bottomRight.x

			&& w_ptr->center.y >= r.topLeft.y && w_ptr->center.y <= r.bottomRight.y)

			list.Remove(w_ptr);

	}

	return 0;

}



int refresh(Icon& i, List<Region>& list)

{

	// i가 list에 있는 region들에 포함되면 0리턴 아니면 1리턴

	for (const Region *w_ptr = list.GetList(); w_ptr != NULL; w_ptr = w_ptr->link) {

		if (i.center.x >= w_ptr->topLeft.x && i.center.x <= w_ptr->bottomRight.x

			&& i.center.y >= w_ptr->topLeft.y && i.center.y <= w_ptr->bottomRight.y)

			return 0;

	}

	return 1;

}