파일 업로드

눈맞춤

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

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) 좌표를 지정하는 두 정수를 포함하고 있습니다.
🖨️ 출력
  • 첫 번째 줄 : 서로를 볼 수 있는 사람 쌍의 수.

💻 예제 입력 1
4 5
0 10
0 -10
10 0
-10 0
🖨️ 예제 출력 1
4

출처: USACO 2013 November Contest, Gold Problem 2. Line of Sight