问题 4895 --4.圆与点对

4895: 4.圆与点对

题目描述

  给定平面直角坐标系 $xOy$ 中的一个圆心在原点,半径为 $r$ 的圆,表示一个障碍。
同时给定 $n$ 个平面直角坐标系内的整点,其中第 $i$ 个点是 $P_i(x_i,y_i)$。保证没有点在圆上或圆内,保证任意两个点的连线不与圆相切。
求有多少个数对 $(i,j)(1 \leq i < j\leq n)$,满足站在 $P_i$ 位置上能看到 $P_j$,即线段 $P_iP_j$ 与圆没有交点。

输入

第一行两个正整数 $n,r$。
接下来 $n$ 行,第 $i$ 行包含两个整数 $x_i,y_i$,表示第 $i$ 个点的坐标,保证不存在两个点,使得这两个点坐标完全相同。

输出

输出仅一行,包含一个整数,表示能互相看见的点的对数。

样例输入输出

输入#1 复制
4 5
0 10
0 -10
10 0
-10 0
输出#1 复制
4

提示

对于 $10\%$  的数据,和样例完全相同。
对于 $40\%$  的数据,$n \leq 1000$。
对于 $100\%$  的数据,$1 \leq 5 \times 10^4$,$|x_i|,|y_i|\leq 10^6$,$1\leq r \leq 10^6$。

序号 标题 作者 发表时间 费用 订购数 操作