CodeForces Round #123 (195D) - Analyzing Polylin

这道题一开始题目看错了...理解了好久才知道题目意思..呃~~其实就是说这些折线叠加..会产生多少拐点...
     假设说题目给的是n条直线..叠加以后只会是1条直线...但是当叠加的不是直线而是折线时..叠加出来的就会有很多拐点...易得n条折线叠加..会得到一条有<=n个拐点的直线..根据题目要求..而这个<=的出现有两种可能: 1、 有折线拐点相同..那么自然叠加一起只会体现出这一个共同的拐点. 2 、通过叠加拐点纠为了180度
     回到题目中来..题目中所有的折线都是在y=0上拐..也就是x轴上..那么要看叠加起来有多少个拐点..就看这些折线的拐点集合有多大..对于每条折线..令y=0很容易求出x=b/k..对于k=0的情况..直接跳过..因为其只会使叠加的折线平行于x轴平移而不会改变形状...将这些拐点存起来..排序后判断有多少个不同的拐点就是答案了..这里由于所有的折线都是在x轴上方..因此不会出现叠加出来的拐点被纠回了180度的情况.
      submit结果WA了...调高精度..过了一半的点..还是WA...精度到1e-50还不行..估计是double已经承受不了这个精度了..去瞄了下别人的AC代码..发现要用long double才行..这个第一次用...很eggache啊...

program:
[cpp] 
#include<iostream> 
#include<algorithm> 
#include<stdio.h> 
#include<string.h> 
#include<cmath> 
#include<queue> 
#define oo 2000000000 
#define ll long long 
using namespace std;   
int n; 
long double a[100005]; 
int main() 
{    
       cin>>n; 
       int i,m=0,ans; 
       double b,k; 
       for (i=1;i<=n;i++)  
       { 
              cin>>k>>b; 
              if (k!=0) a[++m]=-(b/k); 
       } 
       sort(a+1,a+1+m); 
        
       ans=0; 
       for (i=2;i<=m;i++)  
          if (fabs(a[i]-a[i-1])>1e-50) ans++; 
       if (m) ans++; 
       cout<<ans<<endl; 
       return 0; 
}