P0739

[Usaco2009 Open]牛绣花cowemb

[Usaco2009 Open]牛绣花cowemb

Bessie 学会了刺绣这种精细的工作。牛们在一块半径为 dd 的圆形布上绣花。它们一共绣了 NN 条直线，每条直线连接圆形布边缘上的两个点，并且没有两条直线经过边缘上的同一个点。

作为一只热爱数学的牛，Bessie 知道每条直线的方程为 ax+by+c=0ax+by+c=0，其中 aa、bb 和 cc 均为整数，且没有两条直线完全重合。不幸的是，有些直线并不穿过圆形布的内部。

圆形布的圆心为原点 (0,0)(0,0)，边界上所有点到原点的距离均为 dd。对于奶牛来说，刺绣作品中直线的交点越多，作品便越有价值。请帮助 Bessie 计算所有在圆形布内部相交的直线对数，也就是说，交点到原点的距离小于 dd 的直线对数。

注意，如果有 33 条直线在圆内同一点相交，则应计为 33 对；如果有 44 条直线共点，则应计为 66 对。

输入格式

第一行包含两个用空格分隔的整数 NN 和 dd。

接下来 NN 行，每行包含 33 个整数 aa、bb 和 cc，表示一条直线的方程 ax+by+c=0ax+by+c=0。

输出格式

输出一个整数，表示在圆形布内部相交的直线对数。

样例输入

2 1
1 0 0
0 1 0

样例输出

1

样例解释

输入说明：

两条直线x=0和y=0.

两条直线在点 (0,0)(0,0) 相交，显然该点到原点的距离小于 11。

数据范围

  • 1≤d≤500001\le d\le 50000；
  • 2≤N≤500002\le N\le 50000；
  • −1000000≤a≤1000000-1000000\le a\le 1000000；
  • −1000000≤b≤1000000-1000000\le b\le 1000000；
  • −1000000≤c≤1000000-1000000\le c\le 1000000；
  • 每条直线满足 aa、bb 中至少有一个非零；
  • 没有两条直线完全重合；
  • 没有两条直线经过圆形布边缘上的同一个点。

来源与许可

本题为 USACO 2009 Open 试题「Cow Embroidery」，题面与测试数据整理自 BZOJ 1573。

样例 1

输入

2 1
1 0 0
0 1 0

输入说明：
两条直线x=0和y=0.

输出

1