[TIOJ] 1882. pC. 最暖的冬天

題目連結:http://tioj.infor.org/problems/1882

---

本題是要求一堆二次函數取min疊加起來後的最大值，因為二次函數疊加起來後其實斜率還是有單調性，因此可以三分搜出答案，不過我不太喜歡寫三分搜，因此就寫了個模擬退火(當初是培訓時有人提了這鬼東東ww)，研究了一下發現滿有趣的，簡單來說就是隨邊挑個起點，走走看如果比較好就走，如果比較差就用$e^{\Delta y \times t}$ 來判斷是否要走下去(這裡的t指的是步數，原本是用溫度)，不過因為本題的斜率有單調性，所以不需要往下(這好像又叫爬山法)。此外我裡面還用了C++的random，發現可調的參數真的變多了，但相對的用起來也沒那麼無腦了XD

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

struct wow{
	double a,b,c;
};
vector<wow> func;
inline double getY(double x);

int main(){
	cin.tie(NULL);ios_base::sync_with_stdio();
	default_random_engine rGen;
	uniform_real_distribution<double> rForm(-1,1);
	auto random = bind(rForm,rGen);
	int n;
	cin>>n;
	func.resize(n);
	for(int i=0;i<n;i++) cin>>func[i].a>>func[i].b>>func[i].c;
	uniform_real_distribution<double> inipos(0,90);
	double x=inipos(rGen);
	double y=getY(x);
	double pace=90;
	const double rate=0.9;
	double minPace=1e-7; 
	while(pace>minPace){
		double newX=x+random()*pace;
		while(newX<0||newX>90)newX=x+random()*pace;
		double newY=getY(newX);
		if(newY>y){
			x=newX;
			y=newY;
		}else pace*=rate;
	}
	cout<<setprecision(6)<<fixed<<x<<endl;
	return 0;
}

inline double getY(double x){
	double rr;bool flag=1;
	for(auto i:func){
		double val = i.a*x*x+i.b*x+i.c;
		if(flag){
			rr=val;
			flag=0;
		}else rr=min(rr,val);
	}
	return rr;
}