[ZeroJudge] [ISSC] b591: 最小容量造船問題

題目連結:https://zerojudge.tw/ShowProblem?problemid=b591

---

今天去打ISSC時的題目，最後沒寫出來，賽後想兩下就知道哪邊爛了，囧。一開始看到題目時，直覺是對y二分搜，後來寫一寫後發現那東東好像不是很好做(雖然大為學長他們後來也還是做了出來...)，想了一段時間後就發現其實將所有的x跟那個x所對應到最小且合法的y畫在平面上，其實他是會是一個凹向下的圖形(類似二次函數)，所以其實可以三分搜(不過那時不知為何我寫了個爬山，囧)，發現這件事後就直接對x三分搜即可。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second
const double eps = 1e-7;

vector<PII> con;
double getY(double);

int main(){
	int n;
	while(scanf("%d",&n), n){
		con.clear();
		for(int i=0;i<n;i++){
			PII x; scanf("%d%d",&x.FF,&x.SS);
			con.PB(x);
		}
		double l=0, r=1e9;
		for(int _=0;_<500;++_){
			if(r-l < eps) break;
			double ll=l+(r-l)/3, rr=l+2*(r-l)/3;
			if(getY(rr) < getY(ll)) l=ll;
			else r=rr;
		}
		double yy = getY(r);
		if(yy<=0) puts("0");
		else printf("%.3lf %.3lf\n", yy, r);
	}
	return 0;
}

double getY(double x){
	double r = -1e9;
	for(int i=0;i<(int)con.size();i++)
		r = max(r, x*con[i].FF+con[i].SS);
	return r;
}