题解 P1883 【函数】

louzhenyu · 2017-10-25 20:33:04 · 题解

没人写题解，所以发个。按照1楼的方法1写的代码，一次AC。

#include <iostream>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;
const int maxN = 10005;
int a[maxN], b[maxN], c[maxN], n;
struct seg{     //如果 e < s，表示这个区间不存在 
    long double s;//区间起点 
    long double e;
};
struct root{ //二次方程的2个根 
    bool exist;
    long double x1;
    long double x2;
};
//计算第i个二次函数的值 
long double getV(int i, long double x){
    return a[i] * x * x + b[i] * x + c[i];
}
//计算方程 ax*x + b*x + c = y 的根 (a != 0)
root getR(int i, long double y){
    root r;
    long double t = b[i] * b[i] - 4 * a[i]*(c[i]-y);
    if(t < 0)    r.exist = false;
    else{
        r.exist = true;
        r.x1 = (-1 * b[i] - sqrt(t)) / (2 * a[i]);
        r.x2 = (-1 * b[i] + sqrt(t)) / (2 * a[i]);
    }
    return r;
}
//求第i个f的最大值，用于二分的上限 
long double getMax(int i){
    if(a[i] == 0){
        if(b >=0)    return getV(i,1000);
        else    return getV(i,0);
    }
    else{
        long double p = -0.5 * b[i] / a[i];//对称轴 
        if(p <= 0)    return getV(i,1000);
        else if(p >=1000)    return getV(i,0);
        else{//对称轴在[0, 1000]之间 
            return max(getV(i,0),getV(i,1000));
        }
    }
}
//求出第i个函数值<=y的区间 
seg getSeg(int i, long double y){
    seg res;
    if(a[i] == 0){
        if(b[i] == 0){
            if(c[i] <= y){
                res.s = 0;
                res.e = 1000;
            }
            else{
                res.s = 0;
                res.e = -1;
            }
        }
        else if(b[i] > 0){
            res.s = 0;
            res.e = (y - c[i]) / b[i];
        } 
        else{
            res.s = (y - c[i]) / b[i];
            res.e = 1000;
        }
    }
    else{//a > 0;
        root r;
        r = getR(i, y);    
        if(r.exist){
            res.s = r.x1;
            res.e = r.x2;
        }
        else{
            res.s = 0;
            res.e = -1;
        }
    }
    if(res.e > 1000)    res.e = 1000;
    if(res.s < 0)    res.s = 0;
    return res;
}
//判断2个区间是否相交，返回相交区间 
seg getJoint(seg s1, seg s2){
    seg s;
    if(s1.e < s1.s || s2.e < s2.s){
        s.s = 0;
        s.e = -1;
    }
    if(s1.e < s2.s || s2.e < s1.s){//不相交 
        s.s = 0;
        s.e = -1;
    }
    else{
        s.s = max(s1.s, s2.s);
        s.e = min(s1.e, s2.e);
    }
    return s;
}
bool check(long double y){
    seg s[maxN];
    seg t;//保存相交区间 
    for(int i = 0; i < n; i++){
        if(i == 0)    t = getSeg(i, y);
        else{
            seg m = getSeg(i, y);
            t = getJoint(t, m);
            if(t.e < t.s)    return false;//如果相交区间不存在, y可以放大     
        }
    }
    return true;//存在相交区间，y可以缩小（包含答案） 
}
int main(){
    int T;
    long double rMax = 0;
    cin>>T;
    for(int i = 0; i < T; i++){
        cin>>n;
        for(int j = 0; j < n; j++){
            cin>>a[j]>>b[j]>>c[j];
            rMax = j == 0 ? getMax(j) : max(rMax, getMax(j));
        }
        long double l = 0.00001, r = rMax+1, res = 0;
        while(fabs(l-r) > 0.00001){
            long double mid = (l + r) / 2;
            if(check(mid)){
                res = mid;
                r = mid;
            }
            else    l = mid;
        } 
        cout<<setprecision(4)<<fixed<<res<<endl;    
    }
    return 0;
}