[ZeroJudge] [ISSC] b591: 最小容量造船問題
題目連結:https://zerojudge.tw/ShowProblem?problemid=b591
今天去打ISSC時的題目,最後沒寫出來,賽後想兩下就知道哪邊爛了,囧。一開始看到題目時,直覺是對y二分搜,後來寫一寫後發現那東東好像不是很好做(雖然大為學長他們後來也還是做了出來...),想了一段時間後就發現其實將所有的x跟那個x所對應到最小且合法的y畫在平面上,其實他是會是一個凹向下的圖形(類似二次函數),所以其實可以三分搜(不過那時不知為何我寫了個爬山,囧),發現這件事後就直接對x三分搜即可。
今天去打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;
}
留言
張貼留言