올림픽 황금 선수

선수마다 실력과 피로도가 시간에 따라 선형으로 변할 때, 어떤 시각 t >= 0에서 실력이 유일하게 최대이고 피로도가 유일하게 최소인 선수의 수를 센다.

어려움8기하이분 탐색정렬구현아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제

리우 올림픽이 끝난 뒤 투자자 모임이 브라질 대표팀 선수 NN명을 지켜보고 있다. 이 모임은 올림픽이 끝난 순간의 실력과 피로도를 선수마다 기록했고 두 값이 각각 일정한 속도로 변한다는 사실도 알아냈다. 올림픽이 끝난 순간을 t=0t = 0으로 둔다.

t=0t = 0에서 선수 ii의 실력은 HiH_i, 피로도는 CiC_i이다. 단위 시간마다 실력은 HitH_{it}만큼, 피로도는 CitC_{it}만큼 변하므로 시점 tt에서 선수 ii의 실력은 Hi+HittH_i + H_{it} t, 피로도는 Ci+CittC_i + C_{it} t이다.

선수 ii가 시점 tt에서 다음 두 조건을 모두 만족하면 그 시점의 황금 선수다.

  • 다른 모든 선수보다 실력이 크다.
  • 다른 모든 선수보다 피로도가 작다.

두 비교는 모두 등호를 포함하지 않는다. 실력이 가장 큰 선수가 둘 이상이거나 피로도가 가장 작은 선수가 둘 이상이면 그 시점에는 황금 선수가 없다. 선수가 한 명뿐이면 그 선수는 모든 시점에서 황금 선수다.

투자자 모임은 황금 선수에게만 투자한다. t0t \ge 0인 실수 시점 가운데 한 번이라도 황금 선수가 된 선수는 투자를 받는다. tt는 얼마든지 커도 되고 t=0t = 0에서 황금 선수인 선수도 투자를 받는다. t<0t < 0에서만 황금 선수였던 선수는 투자를 받지 못한다. 투자를 받는 선수가 몇 명인지 구하라.

입력

첫 줄에 선수 수 NN이 주어진다. 다음 NN개 줄 가운데 ii번째 줄에는 네 정수 HiH_i, HitH_{it}, CiC_i, CitC_{it}가 공백으로 구분되어 주어진다. 순서대로 올림픽 직후의 실력, 실력 변화율, 올림픽 직후의 피로도, 피로도 변화율이다.

  • 1N1051 \le N \le 10^5
  • 106Hi,Hit,Ci,Cit106-10^6 \le H_i, H_{it}, C_i, C_{it} \le 10^6
  • Hit0H_{it} \ne 0이고 Cit0C_{it} \ne 0

출력

투자를 받는 선수의 수를 한 줄에 출력한다.