跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2796. Analyzing Polyline

    ID: 2802 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>计算几何数学排序编程与模拟提高难度共享题库Codeforces英文题面题目来源题面语言

Analyzing Polyline

题目描述

D. Analyzing Polyline
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As Valeric and Valerko were watching one of the last Euro Championship games in a sports bar, they broke a mug. Of course, the guys paid for it but the barman said that he will let them watch football in his bar only if they help his son complete a programming task. The task goes like that.

Let's consider a set of functions of the following form:

Let's define a sum of n functions y1(x),...,yn(x) of the given type as function s(x)=y1(x)+...+yn(x) for any x. It's easy to show that in this case the graph s(x) is a polyline. You are given n functions of the given type, your task is to find the number of angles that do not equal 180 degrees, in the graph s(x), that is the sum of the given functions.

Valeric and Valerko really want to watch the next Euro Championship game, so they asked you to help them.

Input

The first line contains integer n (1≤n≤105) − the number of functions. Each of the following n lines contains two space-separated integer numbers ki,bi (-109≤ki,bi≤109) that determine the i-th function.

Output

Print a single number − the number of angles that do not equal 180 degrees in the graph of the polyline that equals the sum of the given functions.

Examples
Input
1
1 0
Output
1
Input
3
1 0
0 2
-1 1
Output
2
Input
3
-2 -4
1 7
-5 1
Output
3

题目来源：fps-www.educg.net-codeforce-1-2833.xml.zip；FPS 共享题包，题包内第 2466 题。保留原作者与原赛事署名。