题目名称	764. [USACO Open09] 牛类刺绣
输入输出	`cowemb.in/out`
难度等级	★★★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	Satoshi 于2016-07-03加入
开放分组	全部用户
提交状态
分类标签	数学计算几何
	分享题解

通过：5，提交：19，通过率：26.32%
FoolMike	100	0.146 s	9.45 MiB	C++
再见	100	0.157 s	7.54 MiB	C++
Satoshi	100	0.486 s	9.66 MiB	C++
石家庄二中教练	100	0.564 s	13.47 MiB	C++
MiracleEEEE	100	0.876 s	3.15 MiB	C++
FoolMike	90	0.126 s	7.16 MiB	C++
王者自由	70	3.611 s	1.44 MiB	C++
Makazeu	70	3.966 s	1.59 MiB	C++
201101	70	3.970 s	1.26 MiB	C++
苏轼	60	4.245 s	1.41 MiB	C++

本题关联比赛
20120416

关于牛类刺绣的近10条评论(全部评论)
回复 @Satoshi : 其实直接统计不过零度角的那部分就行。注意不合法区间要筛掉，注意long double FoolMike 2017-07-12 19:47 2楼
我们画图可以发现，如果两个线段相交，则每个线段的两个端点(在圆周上)所对应的劣弧极角区间一定相交,我们计算出这些极角区间，离散化，然后求出有多少对区间相交即可(需要使用线段树/树状数组/平衡树维护),时间复杂度为$\Large O(n\log_2n)$ 连立方程, $\Large ax+by+c=0$ $\Large x^2+y^2=r^2$ 得 $\Large x=\frac {-ac\pm \sqrt {(ac)^2+(b^2r^2-c^2)(a^2+b^2)}}{a^2+b^2}$ $\Large y=\frac {-bc\pm \sqrt {(bc)^2+(a^2r^2-c^2)(a^2+b^2)}}{a^2+b^2}$ 然而，一些极角区间可能跨过了0度线,我们不妨称之为智障区间，比如[300,30],我们把这些区间记两次数，以[300,390]计算一次，[-60,30]计算一次，可以保证这两次智障区间和非智障区间相交的对只会被计算一次，然而智障区间和智障区间相交的对被计算了两次，再对所有的智障区间计算一次并减掉即可 Satoshi 2016-07-03 14:24 1楼

764. [USACO Open09] 牛类刺绣

★★★☆ 输入文件：cowemb.in 输出文件：cowemb.out 简单对比
时间限制：1 s 内存限制：128 MiB

Bessie研究了牛类刺绣的详情：牛在刺绣时，要先将一块布固定在一个半径为$d(1 <= d <= 50,000，d为整数)$的环状铁箍上，然后在布上进行刺绣，她们要在布上绣$N(2 <= N <= 50,000)$条直线段，每条线的两端都在铁环的边缘上，任意两个刺绣点都不在同一位置。

经过数学学习，Bessie知道了每条直线的公式$ax+by+c=0$，为方便起见，$a,b,c$都是整数$(-1,000,000 <= a,b,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）$