아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

아침 태권도

시간 제한1초메모리 제한1024 MB

요약
원점에서 볼 때 다른 점에 가려지지 않는 점의 개수를 센다. 즉, 원점과 점을 잇는 선분 위에 다른 점이 없는 점의 수를 구한다.
난이도

보통10점 중 4점

유형
해시맵, 수학, 기하, 정렬
정답자
아직 제출이 없습니다

문제

KSA의 1학년 학생들은 매일 아침 졸업을 하기 위해 아침 태권도를 해야 한다.

태권도장은 2차원 좌표평면으로 표현할 수 있고, 이때 사범님은 원점에 앉아있다. NN명의 1학년 학생들은 11번부터 NN번까지의 번호로 구분되며, ii번 학생의 위치는 (X_i,Y_i)(X\_i, Y\_i)이다. 태권도 사범님은 ii번 학생이 다른 학생에게 가려지지 않는 경우에만 볼 수 있다. 즉, 원점과 (X_i,Y_i)(X\_i, Y\_i)를 이어 선분을 만들었을 때, 선분 위에 위치한 다른 학생이 아무도 없을 때 사범님은 ii번 학생을 볼 수 있다.

1학년 학생들은 너무 공부를 많이 하여 매우 졸리기 때문에, 사범님에게 보이는 학생들만 태권도를 열심히 한다. 학생들의 위치 정보가 주어졌을 때, 태권도를 열심히 하는 학생들은 몇 명인지 구하시오.

입력

첫 번째 줄에 정수 NN이 주어진다.

i+1i + 1번째 줄에 두 정수 X_i,Y_iX\_i, Y\_i가 공백으로 구분되어 주어진다. (1≤i≤N)(1 \leq i \leq N)

출력

태권도를 열심히 하는 학생들은 몇 명인지 출력한다.

제한

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • −104≤X_i,Y_i≤104-10^4 \leq X\_i, Y\_i \leq 10^4
  • 모든 ii에 대해 (X_i,Y_i)≠(0,0)(X\_i, Y\_i) \neq (0, 0)
  • (X_i,Y_i)=(X_j,Y_j)(X\_i, Y\_i) = (X\_j, Y\_j)인 서로 다른 ii, jj가 존재하지 않음

예제2

  1. 예제 1

    입력
    7
    1 2
    2 4
    -2 2
    -4 4
    -1 0
    -3 0
    2 -1
    
    예상 출력
    4
    
  2. 예제 2

    입력
    5
    1 2
    2 4
    1 1
    3 2
    2 2
    
    예상 출력
    3