解题思路
有序三元 (p,q,r) 要求 p 到 q、p 到 r 的欧氏距离相等,且三点互异。关键是固定原点 p 之后,看其余点按距离如何扎堆。
- 枚举原点 p。对每个 p,扫描其余 m−1 个点,按到 p 的距离分桶。比较平方距离 dx2+dy2,既避开开方的浮点误差,又与原距离相等性完全一致。
- 某一距离上有 c 个点时,从中挑两个做成有序对 (q,r),方案数是 P(c,2)=c⋅(c−1),不是组合数 C(c,2)。题面明确 (p,q,r) 与 (p,r,q) 各计一次。
- 把所有原点、所有桶的贡献加起来即为答案。点数互异,不会出现距离为 0 的桶。
- 坐标到 ±105,平方距离最大约 8×1010,必须用 64 位整数存 dx2+dy2;答案最大约 m(m−1)(m−2),同样要用 64 位。常见假解:用
int 乘平方溢出、用浮点比距离、只计组合不计排列、三重循环 O(m3)。
题目内容
整点网格铺成的平面上,散落着若干座雷达站,每座站都用一对整数记下它的位置。
把其中一座站设成探测原点之后,若它到另外两座彼此不同的站,欧氏间距恰好相等,就把这三座站记成一次等心探测。
现给出 m 座两两位置不同的站 loc,第 p 座写作 loc[p]=[up,vp]。
所谓等心探测组,指有序三元 (p,q,r):从 p 到 q 的欧氏间距等于从 p 到 r 的欧氏间距。间距按平面欧氏度量来算。请统计这样的有序三元一共出现多少次。
排列会计入次数:(p,q,r) 一旦成立,把后两项对调得到的 (p,r,q) 要再记一次。
输入描述
首行给出站点总数 m。
随后连续 m 行,每一行是两个整数 up 与 vp,对应一座站的横纵坐标。
读入先后对应编号 1,2,…,m。
3≤m≤2×103
−105≤up,vp≤105
各站点位置两两不重合
输出描述
输出一个整数,表示等心探测组的总次数。
样例1
输入
4
0 0
0 3
3 0
3 3
输出
8
说明
四座站落在边长为 3 的正方形顶点上。
- 以 (0,0) 为原点:到 (0,3)、(3,0) 的间距都是 3,到 (3,3) 为 32,因此有序对有 2 组
- 其余三座顶点情形相同
- 总次数 4×2=8
样例2
输入
3
0 0
4 0
2 3
输出
2
说明
三座站构成等腰三角形。
- 以 (2,3) 为原点:到 (0,0) 与到 (4,0) 的间距都是 13,得到 (p,q,r) 与 (p,r,q) 各一次
- 以 (0,0) 或 (4,0) 为原点时,到另外两座的间距不相等
- 总次数为 2