思路
维护一个二维数组pix[ ][ ]模拟窗口像素 in: 数组内坐标 out:所属窗口编号(1. 多窗口共有,以顶部窗口为准, 2. 单个窗口独有)
维护两个PII类型数组l[ ], r[ ]储存输入的窗口坐标信息 in: 窗口号 out:x:坐标系中横坐标, y:坐标系中纵坐标
核心思想:因为坐标系中变量的增长方向和数组的增长方向不完全相同,所以采取mapping,认为y是r,也就将坐标系坐标转化为合理的数组坐标。注意:此时pix[ ][ ]的大小应该分别用y, x的上限确定。
步骤上:
首先读入各窗口坐标,按照每个窗口的数据,在pix中模拟填写编号。
然后维护一个inow表示当前顶部窗口标号。
接着进行m次操作,每次操作进行3类判断(1. pix值为0(无对应窗口) 2.属于顶层窗口(仅输出inow) 3.属于其他窗口,进行inow更新和像素覆盖)
像素覆盖的意义:
对于顶层窗口的判断,我们其实可以直接通过坐标系坐标判断,那么为什么要进行像素覆盖呢?
怕的是进行第3类判断时出错!其他窗口A被点击成了顶层窗口,之后又变成其他窗口,假设他跟另外一个窗口B有公共部分C且不属于目前的顶层窗口,这种情况下如果当时A窗口没进行像素覆盖,那么难以保证公共部分C属于他,但C本应属于他,因为“退役”下来的他有次高优先级(没什么用),对于C来说就是最高优先级(有用)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 2600, M = 1500;
typedef pair<int, int> PII;
int pix[M][N];
PII l[15], r[15];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d%d", &l[i].x, &l[i].y, &r[i].x, &r[i].y);
for(int row = l[i].y; row <= r[i].y; row++)
for(int col = l[i].x; col <= r[i].x; col++)
{
pix[row][col] = i;
}
}
int inow = n;
while(m--)
{
int x, y;
cin >> x >> y;
if(pix[y][x] == 0) printf("IGNORED\n");
else if(pix[y][x] == inow) cout << inow << endl;
else
{
inow = pix[y][x];
for(int row = l[inow].y; row <= r[inow].y; row++)
for(int col = l[inow].x; col <= r[inow].x; col++)
{
pix[row][col] = inow;
}
cout << inow << endl;
}
}
return 0;
}