#1405. 曼哈顿距离

曼哈顿距离

【题目描述】

在平面直角坐标系中,设两点A(xa,ya)和B(xb,yb),定义该两点的“曼哈顿距离”为d(A,B)=|xa-xb|+|ya-yb|。

现有N个整点(整点指的是坐标均为整数的点),请问这些点是否满足以下两个要求之一?

①存在互异的三点A,B,C,使得d(A,B)=d(A,C);

②存在互异的四点A,B,C,D使得d(A,B)=d(C,D)。

【输入格式】

第一行是一个正整数T,表示测试数据的组数。

对于每组测试数据,第一行是一个正整数N,表示点的总数;之后N行,每行包含两个非负整数xi,yi,表示第i个点的坐标。注意可能存在重合的点。

【输出格式】

每组数据输出1行。若这些点满足要求①②之一则输出Yes,否则输出No。

【输入输出样例】

【输入样例1】

1
5
0 0
10 20
30 50
60 10
50 20

【输出样例1】

Yes

【输入样例2】

1
5
0 0
10 20
30 50
60 1
50 2

【输出样例1】

No

【数据规模及约定】

T<=10^5,N<=10^5。在一个测试文件中ΣN<=2*10^5。0<=xi,yi<=10^5

本题共10个测试文件,部分测试点满足如下限制条件 image