• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            The 2010 ACM-ICPC Asia Chengdu Regional Contest Error Curves 三分法求凸函數極值

            Error Curves

            Time Limit: 2 Seconds      Memory Limit: 65536 KB

            Josephina is a clever girl and addicted to Machine Learning recently. She pays much attention to a method called Linear Discriminant Analysis, which has many interesting properties.

            In order to test the algorithm's efficiency, she collects many datasets. What's more, each data is divided into two parts: training data and test data. She gets the parameters of the model on training data and test the model on test data.

            To her surprise, she finds each dataset's test error curve is just a parabolic curve. A parabolic curve corresponds to a quadratic function. In mathematics, a quadratic function is a polynomial function of the form f(x) = ax2 + bx + c. The quadratic will degrade to linear function if a = 0.

            Quadric Function

            It's very easy to calculate the minimal error if there is only one test error curve. However, there are several datasets, which means Josephina will obtain many parabolic curves. Josephina wants to get the tuned parameters that make the best performance on all datasets. So she should take all error curves into account, i.e., she has to deal with many quadric functions and make a new error definition to represent the total error. Now, she focuses on the following new function's minimal which related to multiple quadric functions.

            The new function F(x) is defined as follow:

            F(x) = max(Si(x)), i = 1...n. The domain of x is [0, 1000]. Si(x) is a quadric function.

            Josephina wonders the minimum of F(x). Unfortunately, it's too hard for her to solve this problem. As a super programmer, can you help her?

            Input

            The input contains multiple test cases. The first line is the number of cases T (T < 100). Each case begins with a number n(n ≤ 10000). Following n lines, each line contains three integers a (0 ≤ a ≤ 100), b (|b| ≤ 5000), c (|c| ≤ 5000), which mean the corresponding coefficients of a quadratic function.

            Output

            For each test case, output the answer in a line. Round to 4 digits after the decimal point.

            Sample Input

            2
            1
            2 0 0
            2
            2 0 0
            2 -4 2
            

            Sample Output

            0.0000
            0.5000
            
            簡明題意:求一堆開口向上的二次函數在[0,1000]范圍上函數值最大值的最小值。
            二次函數的子集仍然為凸函數,所以可以用三分法求極值。精度實在很蛋疼,這題要求值域精確到1e-4,但是定義域沒說精確到多少,結果死wa,卡到1e-10終于過了。。
            貼代碼
             1# include <cstdio>
             2# include <cmath>
             3using namespace std;
             4int n;
             5int data[10001][3];
             6# define max(a,b) ((a)>(b)?(a):(b))
             7double cal(double mid)
             8{
             9   double res=-1e26;
            10   for(int i=0;i<n;i++)
            11     res=max(res,data[i][0]*mid*mid+data[i][1]*mid+data[i][2]);
            12   return res;
            13}

            14int main()
            15{
            16    int test;
            17    scanf("%d",&test);
            18    while(test--)
            19    {
            20       scanf("%d",&n);
            21       for(int i=0;i<n;i++)
            22         scanf("%d%d%d",&data[i][0],&data[i][1],&data[i][2]);
            23       double s=0.0,e=1000.0;
            24       double last=s;
            25       while(fabs(e-s)>1e-10)
            26       {
            27       
            28         double m1=(s+e)/2.0,m2=(m1+e)/2.0;
            29         if(cal(m1)<cal(m2))
            30           e=m2;
            31         else 
            32           s=m1;
            33       }

            34       printf("%.4lf\n",cal(e));
            35    }

            36    return 0;
            37}

            38
            39

            posted on 2010-11-16 00:50 yzhw 閱讀(801) 評論(0)  編輯 收藏 引用 所屬分類: numberic

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            99久久精品免费看国产一区二区三区 | 日产精品久久久久久久性色| 久久久精品人妻一区二区三区蜜桃| 国产aⅴ激情无码久久| 亚洲精品无码久久千人斩| 久久久精品久久久久久| 久久亚洲私人国产精品vA| 精品人妻久久久久久888| 亚洲国产成人乱码精品女人久久久不卡| 久久久久国产精品熟女影院| 伊人久久大香线蕉无码麻豆| 久久精品国产2020| 国产精品免费久久久久影院| 国产精品免费福利久久| 久久国产视屏| 久久99精品国产麻豆宅宅| 久久精品a亚洲国产v高清不卡| 国产精品日韩深夜福利久久| 亚洲伊人久久大香线蕉综合图片| 久久久久国产精品| 国产精久久一区二区三区| 亚洲精品美女久久777777| 久久亚洲国产成人影院网站| 欧美午夜精品久久久久久浪潮| 久久精品国产一区二区三区| 久久精品国产精品亚洲毛片| 国产aⅴ激情无码久久| 性做久久久久久久久老女人| 品成人欧美大片久久国产欧美| 久久天天躁狠狠躁夜夜avapp| 久久大香萑太香蕉av| 久久国产免费直播| 伊人热热久久原色播放www| 中文字幕亚洲综合久久2| 久久亚洲中文字幕精品一区| 2021少妇久久久久久久久久| 久久久精品国产亚洲成人满18免费网站 | 久久偷看各类wc女厕嘘嘘| 国产亚洲精品久久久久秋霞 | 一极黄色视频久久网站| 日韩欧美亚洲综合久久影院Ds|