P2950 [USACO09OPEN] Bovine Embroidery G

题目描述

Bessie 已经掌握了奶牛刺绣的精细艺术。奶牛们将布料装在一个半径为整数 $d(1 \le d \le 5 \times 10^4)$ 的圆形绣花箍上进行刺绣。他们要缝 $N(2 \le N \le 5 \times 10^4)$ 条线,每条线都是从绣花箍边缘上的一个点直线缝到另一个点(绣花箍边缘上不会有两条线共享同一个端点)。 Bessie 数学很好,他知道每条直线线段的方程都可以表示为 $ax + by + c = 0$ 的形式。方便的是,$a,b,c$ 都是整数($-10^6 \le a,b,c \le 10^6$),更方便的是,没有两条线完全重合。 也许不那么方便的是,Bessie 知道他的系数集合中还包括一些线段,它们看起来并不穿过绣花箍的内部。他对此深感遗憾。 原点 $(0,0)$ 恰好是绣花箍的中心,因此绣花箍边缘上的所有点与原点距离都是 $d$。每条线的方程中,系数 $a$ 和 $b$ 至少有一个非零。 奶牛刺绣的艺术价值取决于线段交点的数量。请帮助 Bessie 计算在布料上(即与原点距离不超过 $d$ 的范围内)相交的线段对的数量。注意,如果三条线恰好交于同一点,那么就算作三对相交;四条线交于同一点,就算作六对相交,依此类推。

输入格式

第 $1$ 行为两个空格分隔的整数 $N$ 和 $d$; 第 $2 \sim N+1$ 行,第 $i+1$ 行表示第 $i$ 条线,包含三个整数 $a,b,c$。

输出格式

输出一行一个整数,表示相交的线段对的数量。

说明/提示

两条直线分别为 $x=0$ 和 $y=0$,它们相交于 $(0,0)$,显然与原点的距离为 $1$。