5573: BZOJ1573:[Usaco2009 Open]牛绣花cowemb
Memory Limit:64 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Bessie学会了刺绣这种精细的工作。牛们在一片半径为d(1 <= d <= 50000)的圆形布上绣花. 它们一共绣了N (2 <= N <= 50000)条直线,每条直线连接布的边缘上的两个点(没有两条线通过边上同一个点)。 作为一只热爱数学的牛,Bessie 知道每条线的公式, ax + by + c = 0. a, b, 和 c 为整数(-1000000 <= a <= 1000000; -1000000 <= b <= 1000000; -1000000 <= c <= 1000000).没有两条线完全重合。 不幸的是, 一部分线不通过圆布的内部. 原点(0,0)在布的正中央, 所有边上的点离原点距离为d. 每条线的公式满足至少a,b中的一个非零. 对于牛来说,刺绣作品中线的交点越多,便越有价值。帮助Bessie计算在圆中相交的线的对数,也就是说交点与原点的距离小于d。注意如果三条线在圆内同一点相交,这算3对线。4线共点->6对线.
输入格式
第1行: 两个空格分开的数, N 和 d 第2..N+1行: 第 i+1 行包含第i条线的参数: a, b 和 c
输出格式
第1行: 一行,包含一个数,为在园内相交的线的对数.
样例输入
2 1 1 0 0 0 1 0 输入说明: 两条直线x=0和y=0.
样例输出
1
提示
两条线在(0,0)相交, 明显离原点距离小于1.
题目来源
Gold