해결한 사람
0
명
정답률
0.00
%
시간 제한
1000
ms
메모리 제한
245
MB
항공 교통 관제사 Arkady는 현재 공중에 있는 n대의 비행기를 관제하고 있다. 모든 비행기는 하나의 직선 좌표축을 따라 움직이며, 그 좌표축의 점 0에 Arkady의 관제소가 있다. 점으로 나타낼 수 있을 만큼 작은 i-th 비행기의 현재 좌표는 xi이고, 속도 vi로 움직이고 있다. xi·vi < 0임이 보장된다. 즉, 모든 비행기는 관제소를 향해 움직이고 있다.
때때로 비행기는 바람의 영향을 받는다. 풍속이 vwind일 때(양수나 정수일 필요는 없다), i-th 비행기의 속도는 vi + vwind가 된다.
기상 보고에 따르면 현재 바람은 [ - w, w] 범위 안의 일정한 속도로 불고 있으며, 양 끝값도 포함된다. 하지만 이 값은 상당히 작아, 어떤 비행기의 속도의 절댓값보다도 작으므로 정확히 측정할 수 없다.
각 비행기는 Arkady의 관제소 위를 통과하는 정확한 순간에 Arkady에게 연락해야 한다. 가능한 어떤 풍속에서 비행기 i와 j가 같은 순간에 Arkady에게 연락하게 되는 비행기 쌍 (i, j) (i < j)의 개수를 Arkady가 세도록 도와야 한다. 이 풍속 값은 서로 다른 쌍마다 같을 필요가 없다.
풍속은 모든 비행기에 대해 같다. 바람은 일정한 속도로 임의로 오랫동안 분다고 가정해도 된다.
첫 줄에는 두 정수 n와 w (1 ≤ n ≤ 100 000, 0 ≤ w < 105) — 비행기의 수와 최대 풍속이 주어진다.
이어지는 n개 줄의 i-th에는 두 정수 xi와 vi (1 ≤ |xi| ≤ 105, w + 1 ≤ |vi| ≤ 105, xi·vi < 0) — i-th 비행기의 초기 위치와 속도가 주어진다.
비행기들은 서로 다르다. 즉, xi = xj이면서 vi = vj인 (i, j) (i < j) 쌍은 존재하지 않는다.
같은 순간에 Arkady에게 연락할 수 있는 비행기의 순서 없는 쌍의 개수를 나타내는 정수 하나를 출력한다.
6 1
-3 2
-2 2
-1 2
1 -2
2 -2
3 -2
9
5 1
-3 2
-3 3
-1 2
1 -3
3 -5
3
첫 번째 예제에서는 다음 3개의 비행기 쌍이 조건을 만족한다.
두 번째 예제에서는 음의 좌표를 가진 3대의 비행기 각각이 나머지 3대의 비행기 각각과 유효한 쌍을 이룰 수 있으므로, 총 9개의 쌍이 있다.