실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
N 명의 사람들(1 ≤ N ≤ 50,000)이 2차원 레스토랑의 서로 다른 지점에 위치해 있습니다. 레스토랑의 중앙에는 큰 원형 기둥이 있습니다. 기둥을 사이에 두고 있는 사람들은 서로를 못 보는데, 기둥이 시야를 가리기 때문입니다. 직선으로 서로 볼 수 있는 사람들의 쌍의 수를 결정해주세요.
기둥은 중심이 (0,0)인 원형으로 반지름 R 입니다. 어떤 사람도 기둥을 구성하는 원에 위치하거나, 기둥에 접하는 직선 위에 위치하지 않습니다. R의 값은 1..1,000,000 범위에 있으며, 각 사람들은 -1,000,000..+1,000,000 범위 내의 정수 좌표를 가진 지점에 위치해 있습니다.
4 5 0 10 0 -10 10 0 -10 0
4
출처: USACO 2013 November Contest, Gold Problem 2. Line of Sight