kotori最近在研究n皇后的问题。
所谓n皇后问题是这样的:一个n*n的地图,上面一共放n个皇后,保证任意两个皇后都不能互相攻击(每个皇后可以攻击同一行、同一列以及同一45度角斜线和135度角斜线上的所有其他皇后)。
kotori思考了很久都无法得出答案,整个人都变成琴梨了。她于是拿了一堆皇后在一个无穷大的棋盘上模拟,按照次序一共放了k个皇后。
但是,皇后的站位太复杂了,kotori甚至不知道是否存在两个皇后会互相攻击。于是她想问问聪明的你,在第i个皇后放置在棋盘上之后,是否存在两个皇后可以互相攻击?
输入描述:
第一行输入一个正整数k,代表总共放置的皇后的个数。(1<=k<=1e5) 接下来的k行,每行两个正整数xi和yi,代表每个皇后的坐标。(1<=xi,yi<=1e9) 之后输入一个正整数t,代表t次询问。(1<=t<=1e5) 接下来的t行,每行一个正整数i,代表询问第i个皇后放置后,是否存在互相攻击的情况。(1<=i<=k) 保证不存在两个皇后放置的位置相同。
输出描述:
共t行。每行对应当前的询问是否存在两个皇后可以互相攻击,若是则输出“Yes”,否则输出“No”
示例1
输入
5 1 2 2 5 3 1 6 7 4 8 2 2 4
输出
No Yes
说明
第四个皇后放置后,第四个和第一个皇后可以互相攻击。
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int k = Integer.parseInt(bf.readLine());
Set<Integer> setX = new HashSet<>();
Set<Integer> setY = new HashSet<>();
Set<Integer> setA = new HashSet<>();
Set<Integer> setS = new HashSet<>();
int flag = 0;
for(int i = 1; i <= k; i++){
String[] temp = bf.readLine().split(" ");
int x = Integer.parseInt(temp[0]);
int y = Integer.parseInt(temp[1]);
if(flag != 0) continue;
if(!setX.add(x) || !setY.add(y) || !setA.add(x+y) || !setS.add(x-y)){
flag = i; //找到第几个皇后是最小不重复的
}
}
int q =Integer.parseInt(bf.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0;i<q;i++){
int index = Integer.parseInt(bf.readLine());
String a = (index<flag||flag==0)?"No":"Yes";
sb.append(a);
sb.append('\n');
}
System.out.print(sb);
}
}
文章评论