自动搬运

查看原文

来自洛谷，原作者为

	fy0123 **

搬运于2025-08-24 21:43:45，当前版本为作者最后更新于2017-12-04 23:15:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

emmmm先%一下楼下。

然后这个题目还是挺巧妙的，考察转化思想。

由于不能暴力枚举两条直线，我们考虑怎样的情况会使得两条直线相交于圆内。

发现只有这种情况：两条线与圆的4个交点相间排列。

如图：

于是把圆拉成线段后就可以转化为线段上的问题。

至于接下来怎么做，我们将圆拉成一条直线以后，把直线与圆的交点标记出来，发现上面有很多对点（就是某条直线与圆的两个交点）。然后假如把每一对点都连起来，会发现相当于求有交集的区间对数。具体可以手动模拟一下。

然后我们需要快速求出这个有交集的区间对数，这个可以用树状数组维护。

代码什么的见我的blog：链接