만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

경주

시간 제한2초메모리 제한512 MB

요약
평행한 트랙에서 출발 위치와 속도가 주어진 n명의 선수 중, 어느 순간 한 직선 위에 놓이는 최대 인원을 구합니다.
난이도

보통10점 중 6점

유형
기하, 수학, 구현
정답자
아직 제출이 없습니다

문제

경주에 참가하는 선수는 nn명이다. 경기장에는 nn개의 직선 트랙이 있고, ii번째 트랙은 수평선 y=iy = i이다.

선수 ii는 점 (si,i)(s_i, i)에서 출발하여 오른쪽으로 속력 viv_i로 달린다. 경주는 끝나지 않으며, 선수들은 멈추지 않는다.

사진작가 다니엘은 이 경주를 지켜보고 있다. 그는 어떤 순간에 같은 직선 위에 놓이는 선수가 최대 몇 명인지 알고 싶어 한다.

입력

첫 줄에 경주 참가자 수 nn이 주어진다. (1≤n≤3001 \le n \le 300)

다음 nn개 줄에는 각 선수의 정보가 주어진다. ii번째 줄에는 선수 ii의 초기 xx좌표 sis_i와 속력 viv_i가 정수로 주어진다. (−106≤si≤106-10^6 \le s_i \le 10^6; 1≤vi≤1061 \le v_i \le 10^6)

출력

경주 중 어떤 순간에 같은 직선 위에 놓이는 선수 수의 최댓값을 한 정수로 출력한다.

예제1

  1. 예제 1

    입력
    3
    0 1
    0 3
    3 2
    
    예상 출력
    3