Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题目背景

无论是哪条世界线,为了重要的同伴,『凤凰院凶真』最终都会如不死鸟涅槃,为改变既定的过去而向世界发起挑战——即使与 Labmem 相处的过往已是分离丧失的未视感。

题目描述

【世界线变动率 -0.275349%】

众所周知,遇到过去的自己很可能引发时间悖论。

冈部伦太郎要测试时间机器的性能。他在『瓦尔基里』本部附近给出了 $N(N\le 50000)$ 个互不相同的实验地点。本部可以看做二维平面上的一个半径为 $R$ 的圆,圆心与原点重合。为了不引发时间悖论,冈伦需要知道这些实验地点有多少对能互相“看到”。

具体而言,冈部想要知道 $N$ 个二维坐标中,有多少个点对之间的连线(线段)与圆(以原点为圆心,半径为 $R$)没有交点。

冈伦不喜欢 corner case,所以没有两点的连线与圆相切。并且由于技术限制,没有点在圆上或圆内。

冈伦拜托你(桶子)帮他计算这个问题。虽然在这条世界线上你和冈伦没有什么交情,但是冈伦答应下周四 v 你 50。

输入格式

第一行两个正整数 $N,R$,表示点的数量和圆的半径。

接下来的 $N$ 行,每行两个整数 $x_i,y_i$,分别表示第 $i$ 个备选地点的横坐标与纵坐标。

输出格式

一行一个整数,表示有多少个点对能互相看到。

输入输出样例

样例输入 #1

4 50 
4 50 
50 4 
4 100 
100 4

样例输出 #1

3

大样例

样例解释

V 我 100,分你一半。

数据范围

对于所有测试点,有 $1\le N\le50000$,$0\text{<} R\le1000,000$ ,$-1000,000\le x_i,y_i\le1000,000$ 。

对于 $40\%$ 的数据,$N\le1,000$ 。

对于 $50\%$ 的数据,$N\le10,000$ 。