CodeForces 195D. Analyzing Polyline（stl）

朱雀 2022-06-02 03:59 145阅读 0赞

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:

![9aa7cc8d021c2b714c30903f33af9cbd_v_1514842827][] Let's define a sum of *n* functions *y*1(*x*), ..., *y**n*(*x*) of the given type as function *s*(*x*) = *y*1(*x*) + ... + *y**n*(*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 *k**i*, *b**i* ( - 109 ≤ *k**i*, *b**i* ≤ 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.

Example

Input

1
    1 0

Output

Input

3
    1 0
    0 2
    -1 1

Output

Input

3
    -2 -4
    1 7
    -5 1

Output

题解：

意思是给你很多根线的k和b，然后线在y=0的下方的全算作y=0，其他的原样，问你有多少条线的夹角不为180度

就是求出每一条线与y=0的交点为（-b/k，0），求出有多少个不同的这样的点就是答案，可以用set或者map

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    #define ll long long
    map<long double,int>p;
    int main()
    {
        int i,j,n;
        int k,b;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d%d",&k,&b);
            if(k)
            {
                p[(long double)-b/k]=1;
            }
        }
        printf("%d\n",p.size());
        return 0;
    }

[9aa7cc8d021c2b714c30903f33af9cbd_v_1514842827]: https://odzkskevi.qnssl.com/9aa7cc8d021c2b714c30903f33af9cbd?v=1514842827