题解 P2950 【[USACO09OPEN]牛绣Bovine Embroidery】
emmmm先%一下楼下。
然后这个题目还是挺巧妙的，考察转化思想。
由于不能暴力枚举两条直线，我们考虑怎样的情况会使得两条直线相交于圆内。
发现只有这种情况：两条线与圆的4个交点相间排列。
如图：
于是把圆拉成线段后就可以转化为线段上的问题。
至于接下来怎么做，我们将圆拉成一条直线以后，把直线与圆的交点标记出来，发现上面有很多对点（就是某条直线与圆的两个交点）。然后假如把每一对点都连起来，会发现相当于求有交集的区间对数。具体可以手动模拟一下。
然后我们需要快速求出这个有交集的区间对数，这个可以用树状数组维护。
代码什么的见我的blog：链接