QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 5373. 投影对称

Statistics

给定平面上的 $n$ 个整点 $(x_i, y_i)$,将 $n$ 个点投影到一条直线 $l$ 上会形成一个 $n$ 元可重点集 $E_l$。若一条过源点的直线 $l$ 称为“好的”,则存在直线上一点 $P$ 使得 $E_l$ 关于 $P$ 对称。

直线上的一个可重点集关于 $P$ 对称的定义为:除去与 $P$ 重合的点,其余点可以两两配对,使得每对点关于 $P$ 对称。

求有多少条“好的”直线。

注意可能会有无穷多条的情况,这时输出 $-1$。

输入格式

第一行,一个数 $n$,表示点的个数。

接下来的 $n$ 行,每行包括两个整数 $x_i, y_i$,表示第 $i$ 个点的坐标。

$1 \leq n \leq 2\,000$,$|x_i|, |y_i| \leq 10^6$,数据可能有重合的点。

输出格式

一行一个数,表示“好的”直线的条数,无穷条则输出 $-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 \leq 3$。

对于子任务 2($20\%$),$n \leq 12$。

对于子任务 3($20\%$),满足特殊性质 1。

对于子任务 4($50\%$),没有任何特殊性质。

特殊性质 1:$n \geq 100$,$y$ 轴以外最多只有 $10$ 个点,然后在 $y$ 轴正半轴随机放置一些不同的点,并在负半轴放上其关于原点的对称点。

对于 $100\%$ 的数据,$1 \leq n \leq 2\,000$,$|x_i|, |y_i| \leq 10^6$,数据可能有重合的点。