FLOJ [FR #113] 柱子

题目链接

 

Solution

首先,能看到这个圆一定能看到这个圆的圆心。

这个不难证明,如果你不能看到圆心,那么必定有处的圆挡住了它的至少一半,而的对称圆则会挡住它的另外一半,你就看不到这个圆了。

那么问题转化为求有多少的满足不存在圆挡住它。

注意,这里的是圆心到的距离。

那么,原点与的连线为

如果能看到,那么对于

都有

首先,约束最强的最多能使

根据扩展欧几里得,在合法范围内,一定存在一个使得上式成立。

所以,应有

化简一下可以得到,

然后我们可以枚举容斥一下,再枚举统计答案。

复杂度

 

Hints

写暴力的时候猜对了结论,结果后面思路就想偏了。

 

Code