Control de finestres en un escriptori virtual V97747

En un escriptori virtual es poden obrir diverses finestres rectangulars. Cada finestra es descriu amb les coordenades (en píxels) de dues cantonades:

• $(x_1,y_1)$: cantonada superior esquerra.

• $(x_2,y_2)$: cantonada inferior dreta.

Es considera que una finestra cobreix un punt $(x,y)$ si el punt és dins o a la vora del rectangle, és a dir, $$x_1 \le x \le x_2 \quad\text{i}\quad y_1 \le y \le y_2.$$ Als jocs de proves sempre es complirà que $x_1 \le x_2$ i $y_1 \le y_2$.

Cal processar una seqüència d’operacions sobre les finestres:

• ADD id x1 y1 x2 y2: s’afegeix (obre) una finestra amb identificador id i coordenades $(x_1,y_1,x_2,y_2)$.

• CLOSE id: es tanca (elimina) la finestra amb identificador id.

• CHECK x y: es pregunta si existeix alguna finestra oberta que cobreixi el punt $(x,y)$.

• TOP x y: es pregunta quina és la finestra més al davant que cobreix el punt $(x,y)$.

Les finestres afegides més tard queden al davant de les anteriors. Per tant, per a una operació TOP, si diverses finestres cobreixen el punt, s’ha de mostrar la que s’ha afegit més recentment i que encara estigui oberta.

Es pot assumir que:

• Un ADD sempre fa referència a un identificador que no està obert en aquell moment.

• Un CLOSE sempre fa referència a un identificador que està obert en aquell moment.

IMPORTANT: En la solució d’aquest problema has d’usar la tupla Punt que està definida de la següent forma:

struct Punt {
  int x, y;
}

Entrada

La primera línia conté un enter $N$ indicant el nombre d’operacions.

A continuació venen $N$ línies, cadascuna amb una operació en un dels formats següents:

• ADD id x1 y1 x2 y2

• CLOSE id

• CHECK x y

• TOP x y

Tots els valors són enters.

Sortida

Per cada operació:

• Per a CHECK x y, s’ha d’escriure YES si almenys una finestra oberta cobreix $(x,y)$, i NO en cas contrari.

• Per a TOP x y, s’ha d’escriure l’identificador id de la finestra oberta més al davant que cobreix $(x,y)$, o NONE si cap finestra cobreix el punt.

• Per a les operacions ADD i CLOSE no s’ha d’escriure res.

Per obtenir més detalls sobre la sortida consulta els jocs de proves públics.