這道題一開始題目看錯了...理解了好久才知道題目意思..呃~~其實就是說這些折線疊加..會產生多少拐點...
假設說題目給的是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;
}
