首页 > 试题广场 >

窗口点击模拟

[编程题]窗口点击模拟

热度指数：1328 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

本题需要让你模拟一下在Windows系统里窗口和鼠标点击的操作，具体如下：
1.屏幕分辨率为3840*2160，左上角坐标为(0, 0)，右下角坐标为(3839, 2159)
2.窗口是一个矩形的形状，由左上角坐标(X, Y)，和宽高(W, H)，四个数字来定位。左上角坐标为(X, Y)、右下角坐标为(X+W, Y+H)，其中左上角坐标一定会在屏幕范围内，其他一些部分可能会超过屏幕范围。
3.窗口的点击和遮挡规则同Windows，但是不考虑关闭窗口、最大化、最小化和强制置顶的情况。即
   3.1 如果发生重叠的话，后面打开的窗口会显示在前面打开的窗口上面
   3.2 当鼠标发生一次点击的时候，需要判断点击到了哪个窗口，如果同个坐标有多个窗口，算点击到最上层的那个
   3.3 当一个窗口被点击的时候，会浮动到最上层

输入描述:

每个测试输入包含1个测试用例
第一行为2个整数N, M。其中N表示打开的窗口数目，M表示鼠标点击的数目。其中0<N,M<1000
接下来N行，每一行四个整数 Xi Yi Wi Hi，分别表示第i个窗口（窗口Id为i，从1开始计数）的左上角坐标以及宽高，初始时窗口是按输入的顺序依次打开。其中 0<=Xi<3840, 0<=Yi<2160, 0<Wi<3840, 0<Hi<2160
再接下来有M行，每一行两个整数 Xj Yj，分别表示接下来发生的鼠标点击坐标。其中 0 <=Xj<3840, 0<=Yj<2160

输出描述:

对于每次鼠标点击，输出本次点击到的窗口Id。如果没有点击到窗口，输出-1

示例1

输入

2 4
100 100 100 100
10 10 150 150
105 105
180 180
105 105
1 1

输出

算法知识视频讲解

是哥哥啊

from collections import OrderedDict

getNumsFromString = lambda x: list(map(int, x.strip().split()))
def isInWindow(loc, window):
    """ 判断点击是否在窗内 """
    x, y, w, h = window
    return loc[0] >= x and loc[0] <= x + w and \
        loc[1] >= y and loc[1] <= y + h

N, M = getNumsFromString(input())

# 读取窗口，越向后表示越上层
windows = OrderedDict() # {loc: id}
for i in range(N):
    x, y, w, h = getNumsFromString(input())
    windows[(x, y, w, h)] = i + 1

# 读取点击操作
ids = [-1 for i in range(M)]
for i in range(M):
    loc = getNumsFromString(input())
    for window, id in list(windows.items())[::-1]:
        # 从顶级向底部判断
        if isInWindow(loc, window):
            windows.move_to_end(window)
            ids[i] = id
            break

print('\n'.join(list(map(str, ids))))

发表于 2020-07-18 19:29:49 回复(0)

takooctopus

#include <iostream>
#include <list>
#include <memory>
class Coordinate{
    private:
    int x;
    int y;
    public:
    Coordinate(int x, int y){
        this->x = x;
        this->y = y;
    }
    int getX(){
        return this->x;
    }
    int getY(){
        return this->y;
    }
    bool isInScreen(){
        return (this->x >=0 && this->x <3840 && this->y >= 0 && this->y < 2160);
    }
    std::list<int> getCoordinate(){
        std::list<int> ret;
        ret.emplace_back(this->x);
        ret.emplace_back(this->y);
        return ret;
    }
};
class Window{
    private:
    Coordinate coordinate;
    int weight;
    int height;
    int order;
    public:
    Window(int x, int y, int weight, int height, int order) : coordinate(x,y){
        this->weight = weight;
        this->height = height;
        this->order = order;
    }
    int getOrder(){
        return this->order;
    }
    bool isInWindow(Coordinate* click){
        return click->getX() >= this->coordinate.getX()
            && click->getX() <= this->coordinate.getX() + this->weight
            && click->getY() >= this->coordinate.getY()
            && click->getY() <= this->coordinate.getY() + this->height;
    }
};

using PSWindow = std::shared_ptr<Window>;
using PUWindow = std::unique_ptr<Window>;
using PUCoordinate = std::unique_ptr<Coordinate>;


int main(){
    int n,m;
    std::cin >> n >> m;
    std::list<PUWindow> windows;
    std::list<PUCoordinate> clicks;
    std::list<int> ans;
    
    //窗口
    for(int i=0; i<n; i++){
        int x,y,weight,height;
        std::cin >> x >> y >> weight >> height;
        PUWindow window = std::make_unique<Window>(x, y, weight, height, i+1);
        windows.emplace_front(std::move(window));
    } 
    
    //点击
    for(int i=0; i<m; i++){
        int x,y;
        std::cin >> x >> y;
        PUCoordinate coordinate = std::make_unique<Coordinate>(x, y);
        clicks.emplace_back(std::move(coordinate));
    }
    for(std::list<PUCoordinate>::iterator c_iter=clicks.begin(); c_iter!=clicks.end(); c_iter++){
        if(!(*c_iter)->isInScreen()){
            ans.emplace_back(-1);
            continue;
        }
        int cur_num = windows.size();
        bool flag = false;
        for(std::list<PUWindow>::iterator w_iter=windows.begin(); w_iter!=windows.end(); w_iter++, cur_num--){
            if((*w_iter)->isInWindow((*c_iter).get())){
                ans.emplace_back((*w_iter)->getOrder());
                windows.emplace_front(std::move(*w_iter));
                windows.erase(w_iter);
                flag = true;
                break;
                
            }
        }
        if(!flag){
            ans.emplace_back(-1);
        }
    }
    
    for(int x:ans){
        std::cout << x << std::endl;
    }
    return 0;
};

这道题用一个链表就能解决的，因为要重新提到最上层，所以使用list的效率比vector更好一些，要是点到了，就扔去最上层。这边多建了几个类，当然也可以不建，直接做判断就行。

发表于 2022-02-18 19:14:33 回复(0)

PDSnoW

利用两个栈模拟鼠标点击窗口的操作，栈里维护的是窗口的ID，每次鼠标点击从第一个栈的栈顶向栈底开始判断鼠标是否点击到某个窗口，并用第二个栈维护窗口之间的上下关系。如果没找到那么返回-1，如果找到了，返回ID，同时将第二个栈的ID按顺序返回到第一个栈，再将找到的ID最后放到第一个栈的栈顶。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] windows = new int[N][4];
        
        Stack<Integer> st1 = new Stack<Integer>();
        Stack<Integer> st2 = new Stack<Integer>();
        for(int i=0;i<N;i++){
            for(int j=0;j<4;j++){
                windows[i][j] = sc.nextInt();
            }
            st1.push(i);
        }
        
        for(int i=0;i<M;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            boolean find = false;
            int index = -1;
            while(!st1.isEmpty()&&!(find)){
               int idx = st1.pop();
               if(windows[idx][0]<=x&&windows[idx][1]<=y&&x<=(windows[idx][0]+windows[idx][2])&&y<=(windows[idx][1]+windows[idx][3])){
                   find = true;
                   index = idx;
                   break;
               }
               st2.push(idx);
            }
            while(!st2.isEmpty()){
                int tmp = st2.pop();
                st1.push(tmp);
            }
            if(find==false){
                System.out.println(-1);
            }
            else{
                st1.push(index);
                System.out.println(index+1);
            }
        }
    }
}

发表于 2020-08-12 11:49:05 回复(0)

Unlimited_Blade_Works

一开始窗口的产生和覆盖比较像栈的操作，后出现的会覆盖之前出现的。但鼠标点击要求被点中的窗口浮动到最上面，这并不属于栈的操作。

考虑用链表。窗口的产生相当于在链表头插入，每次插入复杂度为O(1)，n个窗口复杂度为O(n)。鼠标点击时，从前往后遍历链表，定位点击的窗口后，将该窗口移动的链表头，单次点击，时间复杂度O(n) + O(1)，m次时间复杂度为O(nm)=O(1e6)。

#include <bits/stdc++.h>
using namespace std;
 
struct node{
    node* next;
    int x1,y1,x2,y2;
    int id;
    node():next(NULL){}
    node(int x1,int y1,int w,int h,int id):x1(x1),y1(y1),x2(x1+w),y2(y1+h),id(id),next(NULL){}
};
 
bool isIn(int x,int y,node* window){
    return x>=window->x1&&x<=window->x2&&y>=window->y1&&y<=window->y2;
}
 
int main(){
    int n,m,x,y,w,h;
    scanf("%d%d",&n,&m);
    node *head = new node();
    for(int i=1;i<=n;i++){
        scanf("%d%d%d%d",&x,&y,&w,&h);
        node* tmp = new node(x,y,w,h,i);
        tmp->next = head->next;
        head->next = tmp;
    }
    while(m--){
        scanf("%d%d",&x,&y);
        node* cur = head->next, *pre = head;
        while(cur&&!isIn(x,y,cur)){
            pre = cur;
            cur = cur->next;
        }
        if(!cur) puts("-1");
        else{
            printf("%d\n",cur->id);
            if(pre!=head){
                pre->next = cur->next;
                cur->next = head->next;
                head->next = cur;
            }
        }
    }
    return 0;
}

发表于 2020-07-24 21:07:20 回复(0)

MALK

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node{int a,b,c,d,num;};
list<node> L;
bool check(node now,int x,int y){
    return (x>=now.a&&x<=now.c&&y>=now.b&&y<=now.d);
}
int main()
{
    int n,m,x,y;
    cin>>n>>m;
    for(int i=1,a,b,w,h;i<=n;i++)
    {
        cin>>a>>b>>w>>h;
        L.push_front({a,b,a+w,b+h,i});
    }
    while(m--)
    {
        cin>>x>>y;
        if(x<0||x>3839||y<0||y>2159)
            cout<<-1<<endl;
        else
        {
            int ans=-1;
            for(auto i=L.begin();i!=L.end();i++)
            {
                if(check(*i,x,y))
                {
                    ans=(*i).num;
                    L.erase(i);
                    L.push_front(*i);
                    break;
                }
            }
            cout<<ans<<endl;
        }
    }
}

是list不香了吗

发表于 2021-08-06 17:37:31 回复(0)

Atodush

链表？

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

struct Window {
    int id;
    int x;
    int y;
    int w;
    int h;

    Window* next;

    Window(int id, int x, int y, int w, int h): id(id), x(x), y(y), w(w), h(h) {
        next = nullptr;
    }
};

void print_window(Window& w) {
    cout << w.x << " " << w.y << " " << w.w << " " << w.h << " " << endl;
}

bool is_in(Window* w, int x, int y) {
    bool x_in, y_in;
    x_in = w->x <= x && (w->x + w->w) >= x;
    y_in = w->y <= y && (w->y + w->h) >= y;
    return x_in && y_in;
}

int main() {
    int n, m;
    cin >> n >> m;

    Window* wins = nullptr;

    for (int i = 0; i < n; i++) {
        int x, y, w, h;
        cin >> x >> y >> w >> h;
        Window* win = new Window((i + 1), x, y, w, h);
        if (wins == nullptr) {
            wins = win;
        } else {
            win->next = wins;
            wins = win;
        }
    }

    Window* head = wins;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        Window* clicked = head;
        Window* prev = nullptr;
        while (clicked != nullptr && is_in(clicked, x, y) == false) {
            prev = clicked;
            clicked = clicked->next;
        }
        if (clicked == nullptr) {
            cout << -1 << endl;
        } else {
            if (prev != nullptr) {
                prev->next = clicked->next;
                clicked->next = head;
                head = clicked;
            }
            cout << clicked->id << endl;
        }
    }

}
// 64 位输出请用 printf("%lld")</vector></iostream>

发表于 2025-09-26 12:26:18 回复(0)

Python

greatofdream

构造窗口ID列表，点击后调整ID列表顺序

import sys
N, M = map(int, sys.stdin.readline().split())
topWindowIndex = [N-i for i in list(range(0, N+1))]
Xs = [[0, 0, 0, 0] for i in range(N+1)]
Xs[0] = [0, 0, 3840, 2160]
for i in range(1, N+1):
    Xi, Yi, Wi, Hi = map(int, sys.stdin.readline().split())
    Xs[i] = [Xi, Yi, Wi, Hi]
for j in range(M):
    Xj, Yj = map(int, sys.stdin.readline().split())
    # in region?
    index, ind = 0, 0
    for ind, i in enumerate(topWindowIndex):
        dx, dy = Xj-Xs[i][0], Yj-Xs[i][1]
        if dx>=0 and dy>=0 and dx<=Xs[i][2] and dy<=Xs[i][3]:
            index = i
            break
    # swap index
    if index==0:
        print(-1)
    else:
        print(index)
        # for i in range(ind-1, -1, -1):
        #     topWindowIndex[i+1] = topWindowIndex[i]
        # topWindowIndex[0] = index
        topWindowIndex.pop(ind)
        topWindowIndex.insert(0, index)

编辑于 2025-04-11 22:52:50 回复(0)

Luoye落

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

struct window{
    int id;
    int x;
    int y;
    int w;
    int h;
    window(int id,int x,int y,int w,int h) : id(id), x(x), y(y),w(w), h(h){}
};

bool IsDJwindow(int x, int y,const window& window){
    return (x >= window.x && x <= window.x + window.w)&&
            (y >= window.y && y <= window.y + window.h) ;
}

int main(){
    
    int N , W;
    cin >> N >> W;
    vector<window> windows;
    //初始化窗口
    for(int i = 0; i < N; ++i){
        int x,y,w,h;
        cin >> x >> y >> w >> h;
        windows.emplace_back(i+1,x,y,w,h);
    }

    //处理点击
    for(int j = 0; j < W; ++j){
        int x,y;
        cin >> x >> y;
        int f_wid = - 1;

        //逆序检查那个窗口被点击到
        for(int i = windows.size() - 1; i >= 0; --i){
            if(IsDJwindow( x, y, windows[i])){
                f_wid = windows[i].id;

                window w = windows[i];
                windows.erase(windows.cbegin() + i);
                windows.emplace_back(w);
                break;
            }
        }
        cout << f_wid << endl;
    }

    return 0;
}

发表于 2025-03-12 02:00:59 回复(0)

Python

冰块十字架

# 最简单的一题了，依然保留了默认的输入结构。
# 思路是将窗口按照输入顺序进行编号，并将窗口的前后顺序看作一个栈。
# 先创建的窗口在底部，后创建的在栈口。
# 针对每一次点击都从栈口开始依次对每个窗口进行判定。
# 被点击到的窗口从栈中取出并放置在栈口，跳出本次点击的循环，开始下一次点击的遍历。
# 如果遍历完所有窗口都没有跳出本次点击的循环，则说明没有点击到任何窗口。

import sys

lines = []

try:
    while True:    # 获取所有输入
        line = sys.stdin.readline().strip()
        if line == '':
            break
        lines.append(line.split())
    N_windows,N_check = int(lines[0][0]),int(lines[0][1])
    windows = lines[1:N_windows+1]
    windows_idx = [i for i in range(N_windows)]    # 将窗口的顺序视为一个栈，越接近栈口越优先点击
    for check in lines[N_windows+1:]:    # 每个鼠标点击都对所有窗口判定一次直到判定点击到窗口
        new_idx = reversed(windows_idx)    # 列表遍历顺序与栈相反，需要先将列表反转
        for i in new_idx:
            Xi,Yi,Wi,Hi = int(windows[i][0]),int(windows[i][1]),int(windows[i][2]),int(windows[i][3])
            if Xi<=int(check[0])<=Xi+Wi and Yi<=int(check[1])<=Yi+Hi:    # 是否在当前窗口内
                print(i+1)
                windows_idx.remove(i)        # 将鼠标点击到的窗口放置到栈口
                windows_idx.append(i)
                break
        else:    # 不在任何窗口内
            print(-1)
            continue
except:
    pass

编辑于 2023-04-20 15:23:52 回复(0)

陶良策

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

void change(vector<vector<int>>& vec, int j, int N)
{
    for(int i=j;i<N-1;i++){
        swap(vec[i][0],vec[i+1][0]);
        swap(vec[i][1],vec[i+1][1]);
        swap(vec[i][2],vec[i+1][2]);
        swap(vec[i][3],vec[i+1][3]);
    }
}

int main() {
    int N,M;
    cin>>N;
    cin>>M;
    vector<vector<int>>windo(N,vector(4,0));
    vector<vector<int>>windocopy(N,vector(4,0));
    vector<vector<int>>click(M,vector(2,0));
    vector<int>seq(N,0);
    
    for(int i=0;i<N;i++)
        cin>>windo[i][0]>>windo[i][1]>>windo[i][2]>>windo[i][3];

    for(int i=0;i<M;i++)
        cin>>click[i][0]>>click[i][1];

    for(int i=0;i<N;i++){
        windocopy[i][0]=windo[i][0];
        windocopy[i][1]=windo[i][1];
        windocopy[i][2]=windo[i][2];
        windocopy[i][3]=windo[i][3];
    }

    int flag=-1;
    for(int i=0;i<M;i++){

        for(int j=N-1;j>=0;j--){

            int X=windo[j][0], Y=windo[j][1], W=windo[j][2], H=windo[j][3];

            int clix=click[i][0], cliy=click[i][1];

            if(clix>=X&&clix<=(X+W) && cliy>=Y&&cliy<=(Y+H)){
                for(int k=N-1;k>=0;k--){
                    if(windo[j][0]==windocopy[k][0]
                       &&windo[j][1]==windocopy[k][1]
                       &&windo[j][2]==windocopy[k][2]
                       &&windo[j][3]==windocopy[k][3]){
                        cout<<k+1<<endl;
                        break;
                    }
                }
                flag=j;
                break;
            }
        }
        if(flag==-1)cout<<-1<<endl;
        else{
            change(windo,flag,N);
            flag=-1;
        }
    }
}
// 64 位输出请用 printf("%lld")

发表于 2023-04-14 12:04:46 回复(0)

牛客809272985号

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int main() {
    stack<vector<int>> frame;
    stack<vector<int>> temp;
    int n,m;
    cin>>n>>m;
    for(int i = 0;i < n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        c+=a;
        d+=b;
        frame.push({i+1,a,b,c,d});
    }
    for(int i = 0;i < m;i++){
        int x,y;
        cin>>x>>y;
        bool blank = true;
        vector<int> topFrame;
        while(!frame.empty()){
            if(frame.top()[1]<=x &&
              frame.top()[3]>=x &&
              frame.top()[2]<=y &&
              frame.top()[4]>=y){
                cout<<frame.top()[0]<<endl;
                blank = false;
                break;
            }
            temp.push(frame.top());
            frame.pop();
        }
        if(blank){
            cout<<-1<<endl;
        }
        else{
            topFrame = frame.top();
            frame.pop();
        }
        while(!temp.empty()){
            frame.push(temp.top());
            temp.pop();
        }
        if(!blank){
            frame.push(topFrame);
        }
    }
    
    
    return 0;
}

发表于 2022-08-13 22:21:41 回复(0)

牛客856530713号

//通过链表维持窗口顺序，初始创建使用头插法，点击窗口移到最前，只需要将当前节点放到第一个。
#include <iostream>
#include <vector>
using namespace std;
 
struct node{
   int index;
   int x,y;
   int w,h;
   node* next;
     
    node():next(nullptr){}
    node(int x, int y, int w, int h):x(x), y(y),w(w), h(h){}
};
 
int main()
{
    node* head = new node();
    //node* p = head;
    int n, m;
    cin >>  n >> m;
    int index = 0;
    while(index < n)
    {
        node* mid = new node();
        cin >> mid->x >> mid->y >> mid->w >> mid->h;
        mid->index = index + 1;
        mid->next = head->next;
        head->next = mid;
        index++;
    }
     
    index = 0;
     
    while(index < m)
    {
        int x,y;
        cin >> x >> y;
        node* p=head, *f = head;
        while(p->next)
        {
            p = p->next;
            if(x >= p->x && y >= p->y && x <= (p->x+p->w) && y <= (p->y + p->h))
            {
                if(f != head)
                {
                    f->next = p->next;
                    p->next = head->next;
                    head->next = p;
                }
                break;
            }
            f = f->next;
        }
        if(p->next == nullptr)
            cout << -1;
        else
            cout << p->index;
        if(index < m-1)
            cout << endl;
        index++;
    }
 
    return 0;
}

发表于 2022-08-12 23:19:57 回复(0)

LL.C

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int[][] windows = new int[N][4];
        
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        for(int i = 0;i < N;i++){
            for(int j = 0;j < 4;j++){
                windows[i][j] = sc.nextInt();
            }
            s1.push(i);
        }
        for(int i = 0;i < M;i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            boolean flag = false;
            int index = -1;
            while(!s1.isEmpty() && !(flag)){
                int indx = s1.pop();
                if(windows[indx][0] <= x && windows[indx][1] <= y && x <= (windows[indx][0]+windows[indx][2]) && y <= (windows[indx][1]+windows[indx][3])){
                    flag = true;
                    index = indx;
                    break;
                }
                s2.push(indx);
            }
            while(!s2.isEmpty()){
                int remp = s2.pop();
                s1.push(remp);
            }
            if(flag == false){
                System.out.println(-1);
            }else{
                s1.push(index);
                System.out.println(index+1);
            }
        }
       
    }
}

发表于 2022-07-26 10:08:26 回复(0)

yyong3

我看很多人的逻辑跟我一样呀，为什么我的只能过一个用例。。而且牛客不能看测试用例这点也太坑了8

#include <iostream>
#include <limits>
using namespace std;
struct node{
    struct node* next;
    int left_up_x,left_up_y,right_down_x,right_down_y,id;
    node(int x,int y,int a,int b,int i):
    left_up_x(x),left_up_y(y),right_down_x(x+a),right_down_y(y+b),id(i),next(nullptr){}
};
int main(){
    int N,M;
    cin>>N>>M;
    node* false_head = new node(0,0,0,0,0);
    int min_left_up_x = std::numeric_limits<int>::max(), 
    min_left_up_y = std::numeric_limits<int>::max(), max_right_down_x = std::numeric_limits<int>::min(),
    max_right_down_y = std::numeric_limits<int>::min();
    for(int i=0;i<N;i++){
        int x,y,a,b;cin>>x>>y>>a>>b;
        node *t = new node(x,y,a,b,i+1);
        t->next = false_head->next;
        false_head->next = t;
        min_left_up_x = std::min(min_left_up_x,t->left_up_x);
        min_left_up_y = std::min(min_left_up_y,t->left_up_y);
        max_right_down_x = std::max(max_right_down_x,t->right_down_x);
        max_right_down_y = std::max(max_right_down_y,t->right_down_y);
    }
    for(int i=0;i<M;i++){
        int x,y;cin>>x>>y;
        if(x<min_left_up_x||y<min_left_up_y||x>max_right_down_x||y>max_right_down_y){
            cout<<-1<<endl;
        }else{
            node* t = false_head->next,*pre = false_head;
            while(t!=nullptr){
                if(x>=t->left_up_x&&y>=t->left_up_y&&x<=t->right_down_x&&y<=t->right_down_y){
                    pre->next = t->next;
                    t->next = false_head->next;
                    false_head->next = t;
                    cout<<t->id<<endl;
                    break;
                }
                pre = t;
                t = t->next;
            }
        }
    }
    return 0;
}

发表于 2021-09-14 09:51:48 回复(0)

永远的小白虾

主要思路就是用一个数组来模拟窗口的层级，越在后面的窗口，越在上面。如果鼠标点击，被数组后面的窗口接收，前面的窗口自然无法接收到点击。

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> windows(n,vector<int>(5,0));//存放最小坐标和最大坐标，以及窗口ID
    for(int i=0;i<n;i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        c=(a+c)>3839?3839:a+c;//越界处理
        d=b+d>2159?2159:b+d;//越界处理
        windows[i][0]=a;
        windows[i][1]=b;
        windows[i][2]=c;
        windows[i][3]=d;
        windows[i][4]=i+1;//id
         
    }
    vector<int> ids(m,-1);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        for(int j=n-1;j>=0;j--)//数组中越后面的窗口代表越在上层
        {
            if(windows[j][0]<=a&&a<=windows[j][2]&&windows[j][1]<=b&&b<=windows[j][3])
            {
               
                ids[i]=windows[j][4];
                //将点击的窗口浮在最上层
                windows.emplace_back(windows[j]);
                windows.erase(windows.begin()+j);
                break;
            }
        }
    }
    for(int i=0;i<m;i++)//输出结果
    {
        cout<<ids[i]<<endl;
    }
    return 0;
}

发表于 2021-08-08 22:29:03 回复(0)

萌死他卡多

#include <iostream>
#include <stack>
using namespace std;
 
struct Window{
    int x1, y1, x2, y2, id;
};
 
stack<Window> s;
stack<Window> rec;
 
int function(int& px, int& py){
    if(px >= 3840 || px < 0 || py >= 2160 || py < 0){
        return -1;
    }
    int windowID = -1;
    while(!s.empty()){
        Window& w = s.top();
        Window best;
        if(px <= w.x2 && px>=w.x1 && py<=w.y2 && py>=w.y1){
            windowID = w.id;
            best = w;
            s.pop();
            while(!rec.empty()){
                s.push(rec.top());
                rec.pop();
            }
            s.push(best);
            break;
        }
        else{
            rec.push(s.top());
            s.pop();
        }
    }
    while(!rec.empty()){
        s.push(rec.top());
        rec.pop();
    }
    return windowID;
}
 
int main(){
    int N,M;
    scanf("%d %d", &N,&M);
    int id = 1;
    while(N--){
        Window w;
        int Xi,Yi,Wi,Hi;
        scanf("%d %d %d %d", &Xi, &Yi, &Wi, &Hi);
        w.x1 = Xi;
        w.y1 = Yi;
        w.x2 = Xi+Wi;
        w.y2 = Yi+Hi;
        w.id = id++;
        s.push(w);
    }
    while(M--){
        int px, py;
        scanf("%d %d", &px, &py);
        cout<< function(px, py) << endl;
    }
}

用2个stack，一个表示先后顺序，一个存查询时不符合的窗口

发表于 2021-07-13 18:23:43 回复(0)

C/C++

牛客216700158号

#include <bits/stdc++.h>
//#include<iostream>
using namespace std;
int main() {
   int n, m;//n,m(0,100)
   int a[1000][4], b[1000][2];//a[][]为窗口数据，b[][]为点击数据
   int c[3][4];//用于窗口位置对调
   int d[1000][4];//用于排布窗口层级
   //xy为左上坐标，wh为宽高
   int i, k;
   int this_click = 10001;
   //0<=Xi<3840, 0<=Yi<2160, 0<Wi<3840, 0<Hi<2160

   cin >> n >> m;   //读入n，m

                   //输入窗口数据
   for (i = 0; i < n; i++) {
       cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
   }
   //将a[][]的值赋给d[][]
   for (i = 0; i < n; i++) {
       for (int j = 0; j < 4; j++) {
           d[i][j] = a[i][j];
       }
   }
   //输入点击数据
   for (i = 0; i < m; i++) {
       cin >> b[i][0] >> b[i][1];
   }

   //一次次寻找点击窗口,i为点击次数，j为点击窗口
   for (i = 0; i < m; i++) {

       //一个个对比鼠标点击位置与窗口范围，从最后一个窗口开始
       for (int j = n - 1; j >= 0; j--) {
           if (b[i][0] >= d[j][0] && b[i][0] <= (d[j][0] + d[j][2])) {
               if (b[i][1] >= d[j][1] && b[i][1] <= (d[j][1] + d[j][3])) {
                   //鼠标点击在窗口范围内-->找到点击的窗口号
                   //第一次点击时，ad顺序相同，j+1为点击的窗口号
                   if (i == 0) {
                       cout << j + 1 << '\n';

                   }
                   //如果不是第一次点击，则与a[][]对比找出窗口号
                   else {
                       for (k = n - 1; k >= 0; k--) {
                           if (d[j][0] == a[k][0]
                               && d[j][1] == a[k][1]
                               && d[j][2] == a[k][2]
                               && d[j][3] == a[k][3]) {
                               cout << k + 1 << '\n';

                               break;//跳出窗口号对比
                           }
                       }
                   }
                    this_click = j;
                   break;//找到被点击的窗口，跳出本次点击查询（for--j）
               }
           }

       }
       //已完成本次查找，开始进行窗口排序，完成后跳出本次点击
       //先确认这次是否点击到了窗口
       if (this_click == 10001) {
           //this_click=10001表示本次并未点击到窗口，无需窗口排序
           //输出-1后退出本次点击
           cout << "-1" << '\n';
       }
       else {
           //本次点击点击到了窗口
           //先保存好本次被点击的窗口
           for (int l = 0; l < 4; l++)
           {
               c[0][l] = d[this_click][l];
           }
           //如果这次点击到的不是最上面的窗口则开始窗口排序
           if (this_click != n - 1) {
               //在被点击窗口右侧的窗口顺序左移一位
               for (int l = this_click; l < n - 1; l++) {
                   for (int j = 0; j < 4; j++)
                   {
                       d[l][j] = d[l + 1][j];
                   }
               }
               //将被点击的窗口放到最上面（最右
               for (int j = 0; j < 4; j++)
               {
                   d[n - 1][j] = c[0][j];
               }
           }
           //将this_click标志置10001
           this_click = 10001;

           //跳出本次点击
       }

   }

}

发表于 2021-03-31 21:29:29 回复(0)

小朋友608

#include<iostream>
#include<vector>
using namespace std;
bool isInWin(int x,int y, vector <int> win){
    if(x<win[0] || y<win[1]  || x>win[2]|| y>win[3])
           return false;
    if(x==win[2])
        if(y==win[3])
               return false;
    return true;
}
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int> > wins(n,vector<int>(4,0));
    vector<int> lists;
    for(int i=0;i<n;i++){
        for(int j=0;j<4;j++){
            cin>>wins[i][j];
        }
        wins[i][2]=wins[i][0]+wins[i][2]>=3840?3840:wins[i][0]+wins[i][2];
        wins[i][3]=wins[i][1]+wins[i][3]>=2160?2160:wins[i][1]+wins[i][3];
        lists.push_back(i);
    }
    int x,y;
    for(int i=0;i<m;i++){
        cin>>x>>y;
        int j=lists.size()-1;
        for(;j>=0;j--){
            if(isInWin(x,y,wins[lists[j]]))
                break;
        }
        if(j==-1)
            cout<<-1<<endl;
        else{
            cout<<lists[j]+1<<endl;
            int t=lists[j];
            lists.erase(lists.begin()+j,lists.begin()+j+1);
            lists.push_back(t);
        }
    }
    
    return 0;
}

发表于 2020-08-02 15:43:39 回复(0)