Cogs 1500. 誤差曲線(三分)

2019-11-11 00:57:16

字體：大中小

供稿：網(wǎng)友

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