#PQJ1087x5373. QOJ 1087_5373

    ID: 2547 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTT 2019枚举

QOJ 1087_5373

标题: 投影对称 - Problem - QOJ.ac

Statistics

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,数据可能有重合的点。