USACO 2013 March Bronze - Cow Race

Bessie과 Elsie는 누가 더 빠른지 정하기 위해 농장에서 경주를 하기로 했다.

두 소는 같은 위치에서 출발하고 같은 시간에 같은 방향으로 달린다. 소들은 일정한 구간을 일정한 속도로 달린다. 예를 들어서, Bessie는 5m/s의 속도로 3초 동안 달리고, 그 다음 10m/s으로 6초 동안 달릴 수 있다.

소들은 당신에게 ‘leadership change’가 일어나는 수를 구해달라고 한다. 어떤 소가 다른 소를 앞지르면 ‘leadership change’라고 한다. 예를 들어서, A가 앞서다가 B가 앞지르거나, A가 앞서다가 B와 일정 시간동안 동등하게 달린 후, B가 앞지르는 경우 모두 ‘leadership change’라고 한다.

PROBLEM NAME : cowrace

INPUT FORMAT

Line 1 : 두 정수 N, M이 주어진다.(1 <= N, M <= 1,000)

Line 2~N+1 : Bessie가 달리는 정보가 두 개의 정수, Bessie의 속도와 그 속도로 달리는 시간으로 주어진다. 모든 정보는 1에서 1,000 사이의 정수이다.

Line N+2~N+M+1 : Elsie의 정보가 위와 동일하게 주어진다.

OUTPUT FORMAT

Line 1 : ‘leadership change’가 일어나는 횟수를 출력하시오.

SAMPLE INPUT

4 3 1 2 4 1 1 1 2 10 2 3 1 2 3 9

SAMPLE OUTPUT

2

http://www.usaco.org/index.php?page=viewproblem2&cpid=259