/*
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;
}
