가시성
시간 제한2초메모리 제한512 MB
격자 위의 점 N개가 주어질 때, 각 점 X의 남쪽으로 열린 60도 부채꼴 내부에 다른 점 Y가 있으면 (X, Y) 쌍마다 사진 한 장을 찍는다. 이렇게 찍히는 사진의 총개수를 구한다.
문제
오트발레드슈브뢰즈 지역 공원에는 지역 동물을 관찰하고 세기 위해 N개의 관측용 가옥이 지어졌다. 또한 동물과 관광객이 더 효율적으로 이동할 수 있도록 격자 축을 따라 길이 지어졌다. 이 길은 모두 수직선(남북 축)과 수평선(서동 축)을 따라 곧게 뻗어 있다.
모든 가옥에는 남쪽을 향한 넓은 관측 창이 있다. 이 창으로는 남쪽과 60도 각도 안에 있는 모든 방향, 즉 평면의 3분의 1을 볼 수 있어 봄과 여름에 멋진 풍경을 보여 준다. 그러나 겨울에는 동물이 집에 머물거나 따뜻한 나라로 이동하고, 나무는 잎을 잃어 너무 앙상해져 거의 보이지 않으므로 사람이 보고 셀 수 있는 것은 다른 관측용 가옥뿐이다.
그래도 SWERC 이후의 야생 나들이로는 여전히 즐겁다. N명의 학생이 이 지역 공원에 가기로 했다. 모든 가옥의 좌표를 알고 있으니 계획을 도와주자. 각 학생은 가옥 하나씩으로 간다.
도착하면 각 참가자는 자기 가옥의 관측 창에 서서 그 자리에서 볼 수 있는 다른 모든 가옥의 사진을 찍을 계획이다. 나들이가 끝나면 학생들이 찍은 사진을 모두 모아야 한다.
관측용 가옥의 좌표 목록이 주어졌을 때, 모으게 될 사진은 몇 장인가?
입력
입력은 다음 줄들로 이루어진다.
- 첫째 줄에는 학생 수이자 관측용 가옥의 수인 정수 N이 주어진다.
- 0 ≤ i < N인 모든 i에 대해 i + 2번째 줄에는 i번째 관측용 가옥의 좌표 Xi와 Yi가 공백으로 구분되어 주어진다.
출력
찍히게 될 사진의 총장수를 나타내는 정수 하나를 한 줄에 출력한다.
제한
- 2 ≤ N ≤ 100 000;
- 모든 i에 대해 0 ≤ Xi ≤ 100 000이고 0 ≤ Yi ≤ 100 000이다.
힌트
가옥 Y가 다른 가옥 X에서 보이는 평면의 3분의 1 경계에 놓이면, 가옥 X에 간 참가자는 Y의 사진을 찍지 않는다. 그 사진은 일부분만 담기기 때문이다. 가옥 Y가 X에서 보이고 Z가 선분 [X,Y] 위에 있으면, 가옥 X에 간 참가자는 가옥 Y만 초점에 담은 사진 한 장과 가옥 Z만 초점에 담은 사진 한 장을 찍는다.