Cogs 1500. 誤差曲線(三分)

2019-11-11 00:25:19

字體：大中小

來源：轉載

供稿：網友

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