← 返回题目列表

Codeforces · 603/D

D. 对反刍动物的思考

中文机器翻译题面 查看原题

孙凯文站在笛卡尔平面的原点思考牛的起源。他注意到平面上有 n 条线 $$\ell_{1}, \ell_{2}, \ldots \ell_{n}$$,每条线都可以用 ax + by = c 形式的方程表示。他还观察到没有两条线是平行的,也没有三条线经过同一点。

对于每个三元组 (i, j, k),使得 1 ≤ i < j < k ≤ n,Kevin 考虑由三条线 $$\ell_{i}, \ell_{j}, \ell_{k}$$ 形成的三角形。如果一个三角形的外接圆经过原点,他称该三角形为原三角形。由于凯文相信牛的生命圈与这些三角形直接相关,因此他想知道由不同线的无序三元组形成的原始三角形的数量。

回想一下,三角形的外接圆是穿过该三角形所有顶点的圆。

输入

输入的第一行包含一个整数 n (3 ≤ n ≤ 2000),即行数。

接下来的 n 行描述 $$\ell_{1}、\ell_{2}、\ldots \ell_{n}$$ 行。这些行的第 i 行包含三个空格分隔的整数 ai、bi、ci (|ai|, |bi|, |ci| ≤ 10 000, ai2 + bi2 > 0),表示 $$\ell_{\overline{2}}$$ 行的方程 aix + biy = ci。

输出

打印一个整数,即三元组 (i, j, k) 的数量,其中 i < j < k,使得 $$\ell_{i}, \ell_{j}, \ell_{k}$$ 行形成一个原始三角形。

示例

输入 #1

4
1 0 0
0 1 0
1 1 -1
1 -1 2

输出 #1

2

输入 #2

3
0 1 1
1 1 2
1 -1 -2

输出 #2

1

注意

请注意,在第一个示例中,一些线条穿过原点。

在第二个示例中,只有一个三元组线: y = 1, x + y = 2, x - y = - 2。它们形成的三角形具有顶点 (0, 2), (1, 1), ( - 1, 1)。该三角形的外接圆有方程 x2 + (y - 1)2 = 1。这确实穿过 (0, 0)。