【算法题】kotori和n皇后

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);}
}