Problem 2220 : The Number of the Real Roots of a Cubic Equation

問題概要

日本語なので本文参照（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2220&lang=jp）

解法

f(x)=ax^3+bx^2+cx+dとして、f(x)のグラフを考える。
f'(x)を考えるとグラフの増減表が書ける。
増減表が書ければ単調な区間がわかるため、それぞれについて二分法を用いれば実数解がわかる。

単調な区間の数は3個または1個（-∞,∞）なので、それぞれの場合について場合わけして二分法を用いる。

ソースコード

int p,m;
double a,b,c;

double f(double x)
{
	return x*x*x+a*x*x+b*x+c;
}
double solve(double lo,double hi,bool dec)
{
	if(hi-lo<EPS)return lo;
	double mid=(lo+hi)/2;
	return (f(mid)<0)^dec?solve(mid,hi,dec):solve(lo,mid,dec);
}

int main()
{
	int n,w,x,y,z; scanf("%d",&n);
	rep(i,n)
	{
		scanf("%d%d%d%d",&w,&x,&y,&z);
		a=1.0*x/w; b=1.0*y/w; c=1.0*z/w;
		p=m=0;
		
		double d=a*a-3*b;
		if(d<0)
		{
			double x=solve(-INF,INF,0);
			if(x<-EPS)m++; else if(x>EPS)p++;
		}
		else
		{
			double p1=(-a-sqrt(d))/3,p2=(-a+sqrt(d))/3;
			double x1=solve(-INF,p1,0),x2=solve(p1,p2,1),x3=solve(p2,INF,0);
			
			if(f(-INF)*f(p1)<=0)
			{
				if(x1<-EPS)m++; else if(x1>EPS)p++;
			}
			if(f(p1)*f(p2)<=0)
			{
				if(x2<-EPS)m++; else if(x2>EPS)p++;
			}
			if(f(p2)*f(INF)<=0)
			{
				if(x3<-EPS)m++; else if(x3>EPS)p++;
			}
		}
		printf("%d %d\n",p,m);
	}
	return 0;
}