레이팅 미적용설명
농부 존의 소 N마리 (1 <= N <= 50,000)가 2차원 목초지의 서로 다른 점에 서 있다. 목초지 한가운데에는 커다란 원형 곡물 저장고가 있다. 저장고를 사이에 두고 반대편에 있는 소들은 저장고가 시야를 가리기 때문에 서로를 볼 수 없다. 직선 시야로 서로를 볼 수 있는 소 쌍의 수를 구하시오.
곡물 저장고는 원점 (0,0)을 중심으로 하며 반지름은 R이다. 저장고에 해당하는 원의 위나 내부에 있는 소는 없으며, 저장고에 접하는 접선 위에 두 마리의 소가 놓이는 경우도 없다. R의 값은 1..1,000,000 범위이고, 각 소는 -1,000,000..+1,000,000 범위의 정수 좌표를 갖는 점에 있다.
제약
입력 형식
첫째 줄에 두 정수 N과 R이 주어진다.
둘째 줄부터 1+N번째 줄까지, 각 줄에 소 한 마리의 (x,y) 좌표를 나타내는 두 정수가 주어진다.
출력 형식
서로를 볼 수 있는 소 쌍의 수를 출력한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
sight.in · 출력을 쓸 파일 sight.out예제 1
입력
4 5
0 10
0 -10
10 0
-10 0출력
4설명
Output details: All 6 pairs can see each-other except the two pairs on opposite sides of the silo.
문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2013-2014 > November > Gold
태그