Analyzing Polyline CodeForces

题意：有n个函数，第i个函数yi(x)=max(ki*x+bi,0)。定义函数s(x)=y1(x)+y2(x)+...+yn(x)。显然函数s的图像是一条折线。求折线上有多少个转折点。

方法：对于每一个函数yi(x)的图像，如果ki等于0，那么没有转折点，否则都有一个转折点，就是在点(-bi/ki,0)处（也就是使得函数值恰好为max(0,0)=0）。如果函数yi和yj有两个不同的转折点，那么它们的和的函数图像显然就会有两个转折点；如果函数yi和yj有两个相同的转折点，那么它们和的函数图像显然只会有一个转折点。对于函数s也是类似的，其转折点个数就是y1到yn中不同的转折点个数，也就是不同的-bi/ki的个数。

 1 #include<cstdio>
 2 #include<set>
 3 using namespace std;
 4 set<long double> s;
 5 int n,k,b;
 6 int main()
 7 {
 8     int i;
 9     scanf("%d",&n);
10     for(i=1;i<=n;i++)
11     {
12         scanf("%d%d",&k,&b);
13         if(k!=0)    s.insert((-(long double)b)/k);
14     }
15     printf("%d",s.size());
16     return 0;
17 }

http://blog.csdn.net/dlpf_c/article/details/76012830