P10497: 我们爱几何

传统题
2.000s 时间限制
128MB 内存限制
1 提交
1 解决

【题目描述】
AngryBacon  ftiasch 是好朋友。ftiasch 酷爱几何,于是 AngryBacon 经常会为 ftiasch 出一些几何 题。这次,他又出了一道题目:
 
给出平面上的 N 个整点,AngryBacon 想选取这 N 个点中的 K 个点,连成一个 K 边形。 正 K 边形的定义为边数为 K 的多边形,要求 K 3,各边相等,各角也相等。 AngryBacon 想知道他最多能取多少个点。
 
【输入】

第一行,1 个整数 T , 表示数据组数。接下来是 T 组数据。 每组数据的第一行包含一个整数 N,表示给定的点数。 接下来的 N 行每行两个整数,分别表示一个点的 x; y 坐标。

【输出】

对于每组数据,输出一行,包含一个整数,表示算最多可取的点数。如果无法连成任何的合法正多边 形,则输出 1

【样例输入】复制
2	
5	
1	0
0	1
1	2
2	1
1	1
4	
0	1
1	2
2	1
1	1
【样例输出】 复制
4
-1
【提示】

• 对于 30% 的数据,1<=N<=50

 

• 对于另外 30% 的数据,1<=N<=200

 

• 对于 100% 的数据,1  <= N <=  1000,  -109 <=x; y<=1091<=T<=20

 

• 保证数据中没有重点。

题目类型~

数学-几何 

咻咻~

提交答案 状态