[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;
...