Problem 1014. -- Friends

1014: Friends

Time Limit: 1 Sec  Memory Limit: 29 MB
Submit: 5  Solved: 1
[Submit][Status][Web Board]

Description

猪国的国王很喜欢交朋友,他希望他的国民也能和他一样,广交天下朋友。于是,他将自己的生日定为“交友节”,每年的这一天,都要在全国举办活动,来让更多的小猪们成为朋友。

今年的活动将在猪国最大的“曲奇广场”举办。曲奇广场是一个圆形的广场,它的周长为L米,活动将在广场的外围(即圆圈上)举办。为方便起见,将广场最北面的地方定为0点,外围上某点的坐标定义成从0点沿外围按顺时针方向走到该点的路程,如图:

上图中,A点的坐标为37,B点的坐标为80。

活动开始前,将会有N只互不认识的小猪被随机安排到广场外围的任意位置,并且任意两只小猪都不处在同一个位置上。在活动开始时,这些小猪就按照各自的速度(单位:米每秒)和方向(顺时针或逆时针)匀速绕广场行走,并且在整个活动的过程中他们各自的行走速度和方向都保持不变。在行走的过程中,如果某一时刻两只互不认识的小猪A和B相遇了(即同时经过同一个位置),那么他们此时将立即成为朋友。整个活动将持续T秒,即T秒后,所有小猪停止走动,此时应该有不少对陌生的小猪成为朋友了吧!

小香猪没有参加这次活动,因为她已经和猪国所有国民都认识了。不过,她对活动结束时,有多少对陌生的小猪变成了朋友很感兴趣,你能帮助她找到答案吗?

Input

输入也许会有多组数据,每一组数据格式如下:
第一行为3个整数L,T,N(1 <= L <= 100000000,0 <= T <= 10000,1 <= N <= 10000)。
接下来N行,每行两个整数X,V(0 <= X <= L-1,0 <= V <= 10000),第i行的X和V分别表示第i头小猪的初始坐标和行走速度。如果V > 0,则表示沿顺时针方向行走,V < 0 则表示沿逆时针方向行走。
输入以3个0结束。

Output

每一组输入数据对应一行输出,每一行输出只有1个整数K,表示在活动结束时共有K对小猪成为了朋友。

Sample Input

3 10 2
1 1
2 1
8 2 3
4 -1
5 2
2 -2
8 5 3
4 -1
5 2
2 -2
8 6 3
4 -1
5 2
2 -2
0 0 0

Sample Output

0
1
2
3

HINT

第1个样例中,两只小猪分别从坐标1和2以相同的速度按顺时针方向行走,因此他们事实上永远也不会相遇。样例2中,经过2秒仅有第2和第3只小猪相遇了,因此只有1对小猪成为了朋友。样例3中,经过5秒第1、2和2、3只小猪发生了相遇,因此结果有2对小猪成为了朋友。样例4中,经过6秒第1、2和2、3还有1、3只小猪都发生了相遇,而第1、3只小猪其实恰好是在第6秒时相遇的,结果有3对小猪成为了朋友。

Source

[Submit][Status]