#PQJ1087x5373. QOJ 1087_5373
QOJ 1087_5373
标题: 投影对称 - Problem - QOJ.ac
The problem was used in the following contests:
给定平面上的 n 个整点 (xi,yi),将 n 个点投影到一条直线 l 上会形成一个 n 元可重点集 El。若一条过源点的直线 l 称为“好的”,则存在直线上一点 P 使得 El 关于 P 对称。
直线上的一个可重点集关于 P 对称的定义为:除去与 P 重合的点,其余点可以两两配对,使得每对点关于 P 对称。
求有多少条“好的”直线。
注意可能会有无穷多条的情况,这时输出 −1。
输入格式
第一行,一个数 n,表示点的个数。
接下来的 n 行,每行包括两个整数 xi,yi,表示第 i 个点的坐标。
1≤n≤2000,|xi|,|yi|≤106,数据可能有重合的点。
输出格式
一行一个数,表示“好的”直线的条数,无穷条则输出 −1。
样例数据
样例 1 输入
3
1 3
2 1
3 3
样例 1 输出
3
样例 2 输入
6
88 -27
115 34
-147 -298
-106 -229
-9 -128
212 135
样例 2 输出
5
样例 3 输入
2
6666 -2333
2333 6666
样例 3 输出
-1
子任务
对于子任务 1(10%),n≤3。
对于子任务 2(20%),n≤12。
对于子任务 3(20%),满足特殊性质 1。
对于子任务 4(50%),没有任何特殊性质。
特殊性质 1:n≥100,y 轴以外最多只有 10 个点,然后在 y 轴正半轴随机放置一些不同的点,并在负半轴放上其关于原点的对称点。
对于 100% 的数据,1≤n≤2000,|xi|,|yi|≤106,数据可能有重合的点。