AOJ-2220: The Number of the Real Roots of a Cubic Equation
問題概要
3次方程式が与えられるので、正の根と負の根の個数を求める問題。
解法
変曲点はすぐに求まるので3分探索して極大値や極小値を求める、とかだと誤差が怖い。なので判別式使って全部整数で処理する。場合分けゲーになって甚だ不本意だけど数学系の問題では仕方ない気もする。ハマりどころとしては、判別式がオーバーフローするとか、Wikipediaに書いてある判別式が間違ってるとか。
#include <cstdio> #include <vector> using namespace std; //ax + b = 0 pair<int,int> solve(int a, int b){ if(b==0) return make_pair(0,0); if(b>0) return make_pair(0,1); return make_pair(1,0); } //ax^2+bx+c=0 pair<int,int> solve(int a, int b, int c){ if(c==0) return solve(a,b); int y4a = -b*b + 4*a*c; if(y4a > 0){ return make_pair(0,0); } if(c < 0){ return make_pair(1,1); } if(b > 0){ return make_pair(0, 2); } return make_pair(2, 0); } //ax^3+bx^2+cx+d=0 pair<int,int> solve(long long a, long long b, long long c, long long d){ if(a < 0){ return solve(-a,-b,-c,-d); } if(d == 0){ return solve(a,b,c); } long long D = b*b*c*c - 4*a*c*c*c - 4*b*b*b*d - 27*a*a*d*d + 18*a*b*c*d; int DD = b*b - 3*a*c; bool minimal_x_plus = (b<0 || DD > b*b), maximal_x_minus = (b>0 || b*b < DD); if(D >= 0){ if(DD == 0){ if(b > 0){ return make_pair(0,3); } else{ return make_pair(3,0); } } if(d > 0){ if(!minimal_x_plus){ return make_pair(0,3); } else{ return make_pair(2,1); } } else{ if(!maximal_x_minus){ return make_pair(3,0); } else{ return make_pair(1,2); } } } else{ if(d > 0){ return make_pair(0,1); } return make_pair(1,0); } return make_pair(-1,-1); } int main(){ int T; scanf("%d",&T); while(T--){ int a, b, c, d; scanf("%d%d%d%d",&a,&b,&c,&d); pair<int,int> ans = solve(a,b,c,d); printf("%d %d\n", ans.first, ans.second); } return 0; }