Cogs 1500. 誤差曲線(三分)

2019-11-11 02:14:44

字體：大中小

供稿：網(wǎng)友

誤差曲線 ★★ 輸入文件：errorcurves.in 輸出文件：errorcurves.out 評(píng)測(cè)插件 時(shí)間限制：1 s 內(nèi)存限制：256 MB 【題目描述】 Josephina是一名聰明的妹子，她最近癡迷于機(jī)器學(xué)習(xí)。她花費(fèi)了大量精力學(xué)習(xí)線性判別分析，因?yàn)槠渲杏胁簧儆腥さ男再|(zhì)。為了測(cè)試算法的性能，她收集了許多數(shù)據(jù)。每組數(shù)據(jù)都分成兩個(gè)部分：訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)。她在訓(xùn)練數(shù)據(jù)中解算模型的參數(shù)，并且在測(cè)試數(shù)據(jù)中測(cè)試這個(gè)模型。令她驚訝的是，她發(fā)現(xiàn)每組數(shù)據(jù)的誤差曲線都是一條拋物線。一條拋物線對(duì)應(yīng)一個(gè)二次函數(shù)。在數(shù)學(xué)中，二次函數(shù)指形如f(x)=ax2+bx+c的多項(xiàng)式函數(shù)。如果a=0，二次函數(shù)就退化為線性函數(shù)。如果只有一條誤差曲線，那么計(jì)算最小的誤差將非常簡(jiǎn)單。但這里有多組數(shù)據(jù)，這意味著Josephina將得到多組誤差曲線。Josephina希望調(diào)整參數(shù)以更好地?cái)M合所有數(shù)據(jù)。因此她必須統(tǒng)計(jì)所有的誤差曲線。也就是說(shuō)，她必須處理許多二次函數(shù)，并得出一條新的錯(cuò)誤曲線來(lái)代表所有的錯(cuò)誤。現(xiàn)在，她正關(guān)注一個(gè)與許多二次函數(shù)有關(guān)的函數(shù)的最小值。這個(gè)新函數(shù)定義如下： F(x)=max(Si(x)),i=1,2,…,n。x的范圍是[0,1000]。Si(x)是一個(gè)二次函數(shù)。 Josephina希望知道F(x)的最小值。不幸的是，用代數(shù)方法求解過(guò)于復(fù)雜。作為一名機(jī)智的程序員，你能幫她解決這個(gè)問(wèn)題嗎？【輸入格式】輸入包含多組數(shù)據(jù)。輸入文件的第1行是1個(gè)正整數(shù)T(T<100)，表示數(shù)據(jù)組數(shù)。每組數(shù)據(jù)的第1行是一個(gè)正整數(shù)n(n<=10000)。接下來(lái)的n行，每行有3個(gè)正整數(shù)a(0<=a<=100),b(|b|<=5000),c(|c|<=5000)，描述一個(gè)二次方程的相應(yīng)系數(shù)。【輸出格式】對(duì)每組數(shù)據(jù)，輸出一行一個(gè)實(shí)數(shù)，即答案。【樣例輸入】 2 1 2 0 0 2 2 0 0 2 -4 2 【樣例輸出】 0.0000 0.5000 【提示】答案允許有不超過(guò)0.01的誤差。【來(lái)源】 **UVa1476 Error Curves 劉汝佳，《算法競(jìng)賽入門經(jīng)典訓(xùn)練指南》表2-14** /*這題卡精度吖卡精度.測(cè)評(píng)插件坑爹啊啊啊啊啊啊啊.so 最后跟風(fēng)判的L orz.這題手畫幾個(gè)函數(shù)把沒(méi)用的曲線去掉就會(huì)神奇的發(fā)現(xiàn)答案有凸性.然后用三分搞凸性. */#include<iostream>#include<cstdio>#define MAXN 100001#define eps 1e-7using namespace std;int n,t,a[MAXN],b[MAXN],c[MAXN];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}double check(double x){ double tot=-1e9; for(int i=1;i<=n;i++) tot=max(tot,double(a[i]*x*x+b[i]*x+c[i])); return tot;}void sanfen(){ double l=0,r=1000,lmid,rmid,ans=0; while(l+eps<=r) { lmid=(2*l+r)/3,rmid=(l+2*r)/3; if(check(lmid)<=check(rmid)) r=rmid,ans=r; else l=lmid; } double x=check(l);