Life Satisfaction
Submit solution
Points:
2 (partial)
Time limit:
1.5s
Python 2
5.0s
Python 3
10.0s
Memory limit:
64M
Authors:
Problem type
Ajay is stuck with a challenge given to him by Akash. Ajay has been given N 2D points. Akash then gives him two 2D points and asks him if they can give him satisfaction for life.
Two points are said to give satisfaction for life if:
- None of the two points are present in the already given N points.
- The Manhattan distance between the two given points is 1 unit.
Akash gives him Q such queries i.e, Q sets of two 2D points. You need to help Ajay figure out if each query can give satisfaction for life or not.
CONSTRAINTS
- 2 ≤ N,Q ≤ 10^5
- -100 ≤ each coordinate of a point ≤ 100
INPUT:
- The first line contains two integers N,Q seperated by a space.
- The next N lines consist of the N 2D points in the format x y
- The next Q lines consist of the queries. Each line has two 2D points x1 y1 x2 y2
OUTPUT:
- For each query, print YES or NO in a newline.
Sample Input:
1 2
2 3
4 3 5 3
3 3 2 3
Sample Output:
YES
NO
Comments