网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Open09]牛类刺绣
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | cowemb.in | 输出文件 | cowemb.out |
Bessie研究了牛类刺绣的详情:牛在刺绣时,要先将一块布固定在一个半径为d(1 <= d <= 50,000,d为整数)的环状铁箍上,然后在布上进行刺绣,她们要在布上绣N(2 <= N <= 50,000)条直线段,每条线的两端都在铁环的边缘上,任意两个刺绣点都不在同一位置。
经过数学学习,Bessie知道了每条直线的公式ax+by+c=0,为方便起见,a,b,c都是整数(-1,000,000 <= a <= 1,000,000; -1,000,000<= b <= 1,000,000; -1,000,000 <= c <= 1,000,000),没有任何两条线是重合的。
有些不便的是,Bessie也知道她的这组直线公式中也包含许多看起来不会经过圆环内部的线,她对此深表遗憾。
原点正好在圆环的正中间,因此所有的刺绣点与原点的距离都是d,每个公式中的a与b都至少有一个不为0。
在牛类的刺绣中,线段相交的的越多,这样的绣品就越值钱,请帮Bessie数数绣在布上的线段(在圆环内)有多少对相交,注意:如果有三条线段相交在同一点,则认为有3对相交,如果四条线交在同一点,则认为有6对相交,以此类推。
输入格式:
第1行,两个空格隔开的整数:N,d;
第2~N+1行,第i+1行用三个整数描述了第i条线:a,b,c;
输出格式:
一行,一个整数,相交的线段对数。
输入输出样例:
cowemb.in
2 1
1 0 0
0 1 0
cowemb.out
1
输出样例解释:
两条线段相交于原点(0,0)。