CCF 201403-2

发表于

窗口

问题描述

　　在某图形操作系统中,有 N 个窗口,每个窗口都是一个两边与坐标轴分别平行的矩形区域。窗口的边界上的点也属于该窗口。窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示位于顶层的窗口里的内容。
　　当你点击屏幕上一个点的时候,你就选择了处于被点击位置的最顶层窗口,并且这个窗口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口,则系统会忽略你这次点击。
　　现在我们希望你写一个程序模拟点击窗口的过程。

输入格式

　　输入的第一行有两个正整数,即 N 和 M。(1 ≤ N ≤ 10,1 ≤ M ≤ 10)
　　接下来 N 行按照从最下层到最顶层的顺序给出 N 个窗口的位置。 每行包含四个非负整数 x1, y1, x2, y2,表示该窗口的一对顶点坐标分别为 (x1, y1) 和 (x2, y2)。保证 x1 < x2,y1 2。
　　接下来 M 行每行包含两个非负整数 x, y,表示一次鼠标点击的坐标。
　　题目中涉及到的所有点和矩形的顶点的 x, y 坐标分别不超过 2559 和　　1439。

输出格式

　　输出包括 M 行,每一行表示一次鼠标点击的结果。如果该次鼠标点击选择了一个窗口,则输出这个窗口的编号(窗口按照输入中的顺序从 1 编号到 N);如果没有,则输出”IGNORED”(不含双引号)。

样例输入

3 4
0 0 4 4
1 1 5 5
2 2 6 6
1 1
0 0
4 4
0 5

样例输出

2
1
1
IGNORED

样例说明

　　第一次点击的位置同时属于第 1 和第 2 个窗口,但是由于第 2 个窗口在上面,它被选择并且被置于顶层。
　　第二次点击的位置只属于第 1 个窗口,因此该次点击选择了此窗口并将其置于顶层。现在的三个窗口的层次关系与初始状态恰好相反了。
　　第三次点击的位置同时属于三个窗口的范围,但是由于现在第 1 个窗口处于顶层,它被选择。

　　最后点击的 (0, 5) 不属于任何窗口。

提交上去90分的代码，暂时不想改了，现在也蛮晚的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import java.util.Scanner;
/**
 * 201403-2
 * */
class window{
	int x1,y1,x2,y2;
	int level;
	int next;
	int beyond;	
}
class point{
	int x,y;
}
public class ccf005 {
public static void main(String args[]){
	Scanner s=new Scanner(System.in);
	window[] wins=new window[10];
	point[] p=new point[10];
	int n=s.nextInt();
	int m=s.nextInt();
	int head=n-1;
	for(int i=0;i<n;i++) {
		wins[i]=new window();
		wins[i].x1=s.nextInt();
		wins[i].y1=s.nextInt();
		wins[i].x2=s.nextInt();
		wins[i].y2=s.nextInt();
		wins[i].next=i-1;//next=-1时invilid
		wins[i].beyond=i+1;//beyond=+n时invilid
	}
	for(int i=0;i<m;i++) {
		p[i]=new point();
		p[i].x=s.nextInt();
		p[i].y=s.nextInt();
	}
	 for(int i=0;i<m;i++) {
		 int j=head;
//		 for(;wins[j].next>-1;j=wins[j].next) {
		 for(;;j=wins[j].next) {
			 if(j==-1)  {System.out.println("IGNORED");
			 break;}
			 if(p[i].x>=wins[j].x1&&p[i].x<=wins[j].x2&&p[i].y>=wins[j].y1&&p[i].y<=wins[j].y2)
			 {
				 if(wins[j].next==-1) {//最后一个页面
					 System.out.println(j+1);
					 wins[wins[j].beyond].next=-1;
					 wins[head].beyond=j;
					 wins[j].next=head;
					 wins[j].beyond=n;
					 head=j;
					 break;		 
				 }else if(wins[j].beyond==n) {//第一个页面
					 System.out.println(j+1);
					 break;
				 }else {
					 System.out.println(j+1);
					 wins[wins[j].beyond].next=wins[j].next;
					 wins[wins[j].next].beyond=wins[j].beyond;
					 wins[j].beyond=n;
					 wins[j].next=head;
					 wins[head].beyond=j;
					 head=j;
					 break;
				 }
			 }	
		 }
//		 if(wins[j].next==-1) {
//			 System.out.println("IGNORED");
//		 }
	 }
}
}

初次总结吧，这类问题真的要好好考虑边界值的问题。

在算法中模拟了双向链表的使用，然而结果并不能如我所愿，只有90分，认真思考过后没有发现那里出现问题。于是准备使用已经封装好的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.awt.List;
import java.util.ArrayList;
import java.util.Scanner;
/**
 * 201403-2
 * */
class window{
	int x1,y1,x2,y2;
	int id;
	public boolean inside(int x,int y) {
		if(x>=this.x1&&x<=this.x2&&y>=this.y1&&y<=this.y2) {
			return true;
		}else {
			return false;
		}
	}
}
public class ccf005 {
public static void main(String args[]){
	Scanner s=new Scanner(System.in);
	ArrayList<window> w=new ArrayList<window>();
	int n=s.nextInt();
	int m=s.nextInt();
	int[] result=new int[10];
	for(int i=0;i<n;i++) {
		window wins=new window();
		wins.x1=s.nextInt();
		wins.y1=s.nextInt();
		wins.x2=s.nextInt();
		wins.y2=s.nextInt();
		wins.id=i+1;
		w.add(wins);
	}
	for(int i=0;i<m;i++) {
		int x=s.nextInt();
		int y=s.nextInt();
		for(int j=w.size()-1;j>=0;j--) {
			if(w.get(j).inside(x, y)) {
				result[i]=w.get(j).id;
				w.add(w.get(j));
				w.remove(j);
				break;
			}
		}
	}
	for(int i=0;i<m;i++) {
		if(result[i]==0)
			System.out.println("IGNORED");
		else System.out.println(result[i]);
	}
	 }
}

这份代码看起来效率是不如之前的代码好，但是相对来说结果正确，而且思路清晰，同样在评测的时候也是100分。