시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB139523839.583%

문제

컴퓨터의 발전은 비단 컴퓨터공학 한 개의 학문을 넘어 수학이나 통계와 같은 영역에서의 발전까지 이루어냈다. 이러한 발전 중 한 가지는 컴퓨터 시뮬레이션을 이용한 확률 실험으로, 현재 그 편리함과 강력함으로 인해 널리 사용되고 있다.

이러한 응용이 강력하다는 것은 간단하게 무리수인 π를 근사하면서 확인할 수 있는데, 어떤 큰 사각형 안에 적당한 원이 존재할 때, 무작위로 수많은 점을 찍은 다음 원 안에 속하는 점의 개수와 원 밖의 영역에 속하는 점의 개수의 비율(확률)을 이용하면 π를 근사할 수 있다.

하지만 π를 구하는 방법은 너무 많이 연구되었으니 이번에는 원의 테두리 위에 세 개의 점을 찍었을 때, 이 세 점이 이루는 삼각형이 예각 삼각형(세 내각의 크기가 모두 90도보다 작은 삼각형)일 확률에 대해 생각해보자.

사실 이 값은 간단한 계산을 통해 0.25임을 알 수 있는데, 실제 시뮬레이션의 결과가 이 값에 가까운지 확인해보기 위해 N개의 점이 주어졌을 때, 이들 중 예각 삼각형이 몇 개 존재하는지 세어보자. (같은 삼각형은 한 번만 센다. 삼각형 abc를 셌으면 bca, cab, cba, ...는 세지 않는다).

입력

먼저, 입력의 첫 번째 줄에는 점의 수 N과 원의 반지름 R이 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ R ≤ 100,000)

그리고 오른쪽 그림과 같이 원 위의 점 P가 점 a를 기준으로 시계 반대 방향으로 θ도 만큼 떨어져 있을 때, 이 점의 위치를 ∅ = θ × 1000으로 표시한다. (즉, x좌표는 R × cos(θ), y좌표는 R × sin(θ)가 된다.) 두 번째 줄 부터는 이 정의에 따라 한 줄에 한 개씩 각 점의 위치가 주어지는데, ∅값이 증가하는 순서로 주어진다. 이때, ∅는 모두 정수이며 (0 ≤ ∅ < 360,000) 모든 점의 ∅값은 다르다.

출력

예각삼각형의 개수를 출력한다.

예제 입력 1

4 71
20375
33576
84908
234600

예제 출력 1

2

예제 입력 2

7 7
11586
108640
114435
150224
248411
287629
340481

예제 출력 2

12

힌트

예제 입력 1의 점과 예각 삼각형을 모두 그려보면 다음과 같다.

계산 과정이나 답의 크기가 32bit 정수형 데이터 타입인 int의 최대 범위를 넘어설 수 있기 때문에 64bit 정수형 데이터 타입인 long long(formatstring: %lld)을 사용해야 한다.

출처

University > 서강대학교 > 2015 Sogang Programming Contest > Champion D번