P1024 一元三次方程求解（递归式二分）

我们判断两点（x）之间是否有根的依据是是否存在 f ( x ) ∗ f ( y ) < 0 f(x) * f(y)<0 f(x)∗f(y)<0
然后由于题目中说根于根之间的差的绝对值大于等于1，以及范围只有-100到100所以我们可以直接枚举，每次+1，缩小范围，然后二分答案精确到0.001即可。

需要注意的是由于我们枚举的时候是从-100到100挨个枚举的所以我们在输出的时候l和r我们只能输出一个，因为一个输出以后另一个由于循环一定会再次到达这个点。所以我们枚举到99，只输出r（l = i, r = i + 1）

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;
typedef long long ll;
const int N = 200007;
const double eps = 1e-3;
//int a[N];
double a, b, c ,d;
int n, m;
double ans;

double f(double x)
{
    return a * x * x * x + b * x * x + c * x + d;
}

void solve(double l, double r)//二分x的坐标找那个点
{
    if(l + eps >= r){
        printf("%.2f ", l);
        return ;
    }
    double mid = (l + r) / 2.0;
    double ans_l, ans_r;
    //if(f(l) == 0)printf("%.2f ", l);
    if(f(mid) == 0)printf("%.2f ", mid);
    if(f(r) == 0)printf("%.2f ", r);
    ans_l = f(l) * f(mid);
    ans_r = f(r) * f(mid);
    if(ans_l < 0)solve(l, mid);
    else if(ans_r < 0)solve(mid, r);
}
//一元三次方程一个根的两端的小范围一定是单调的所以可以用二分
int main()
{
    scanf("%lf%lf%lf%lf", &a, &b, &c, &d);

    for(double i = -100; i <= 99; ++ i){
        if(f(i) * f(i + 1.0) <= 0){//缩小范围，小于0说明有根
            solve(i, i + 1.0);
        }
    }
    return 0;
}