三分（洛谷P3382）
题目大意
给出一个N次函数，保证在\([l,r]\)内存在一点x使得\([l,x]\)上单调递增，\([x,r]\)上单调递减，求出x的值。
解题思路
三分区间，对左端点与右端点的函数值进行比较缩小区间，直到所求x达到精度要求。
未知的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
double L,R;
cin>>n>>L>>R;
vector<double>a(n+1);
for(int i=0;i<=n;i++)cin>>a[i];
auto solve=[&](double k){
double ans=0;
for(int i=0;i<=n;i++)ans=ans*k+a[i];
return ans;
};
while(R-L>=1e-6){
double k=(R-L)/3;
if(solve(L+k)>solve(R-k))R-=k;
else L+=k;
}
cout<<fixed<<setprecision(5)<<L<<endl;
return 0;
}
三分·三分求极值 （hihocoder 1142）
题目大意
求一个抛物线与某一点的最短距离。
解题思路
三分区间，通过比较求得的左端点距离与右端点距离缩小区间直到达到精度要求。
未知的代码
#include<bits/stdc++.h>
using namespace std;
int main(){
double a,b,c,x,y,l=-2e2+5,r=2e2+5;
cin>>a>>b>>c>>x>>y;
auto solve=[&](double k){
double func=a*k*k+b*k+c;
double res=hypot(x-k,y-func);
return res;
};
while(r-l>1e-8){
double k=(r-l)/3;
if(solve(l+k)<solve(r-k))r-=k;
else l+=k;
}
cout<<fixed<<setprecision(3)<<(solve(l)+solve(r))/2<<endl;
return 0;
}
Line belt（hdu 3400）
题目大意
二位坐标上四个点A,B,C,D，AB段速度为P，CD段速度为Q，其余位置速度为R，求A到D的最短时间。
解题思路
分析知，点A将从AB段的某点离开，进入CD段的某点到D。（都包含端点）那么使用三分嵌套分别求出AB离开点和CD进入点即可得到答案。
未知的代码
#include<bits/stdc++.h>
using namespace std;
struct point{
double x,y;
point (){}
point (double x,double y):x(x),y(y) {}
point operator * (int a){
return point (x*a,y*a);
}
point operator / (int a){
return point(x/a,y/a);
}
point operator + (point a){
return point (x+a.x,y+a.y);
}
point operator - (point a){
return point (x-a.x,y-a.y);
}
}a,b,c,d;
int P,Q,R;
const double eps=1e-9;
double dis(point x,point y){
return hypot(x.x-y.x,x.y-y.y);
// return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double solve(point l,point r){
return dis(a,l)/P+dis(l,r)/R+dis(r,d)/Q;
}
double find(point l,point r,point k)
{
double ans=1e8;
do
{
point ll=((l*2)+r)/3;
point rr=(l+(r*2))/3;
double ans1=solve(k,ll);
double ans2=solve(k,rr);
ans=min(ans1,ans2);
if(ans1>ans2)l=ll;
else r=rr;
}while(dis(l,r)>eps);
return ans;
}
double find(point l,point r)
{
double ans=1e8;
do
{
point ll=((l*2)+r)/3;
point rr=(l+(r*2))/3;
double ans1=find(c,d,ll);
double ans2=find(c,d,rr);
ans=min(ans1,ans2);
if(ans1>ans2)l=ll;
else r=rr;
}while(dis(l,r)>eps);
return ans;
}
int main() {
int t;
cin>>t;
while (t--) {
cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y>>P>>Q>>R;
cout<<fixed<<setprecision(2)<<find(a,b)<<endl;
}
return 0;
}
期末考试（洛谷P3745）
题目大意
期末考试后，参与考试的n个同学的最晚期望出全部成绩的时间为\(t_i\)，m门课程的出分时间为\(b_i\)，每个同学每多等一天出分就会产生C的不愉快度，问通过以下两种操作后最小的不愉快度之和是多少？
- 让学科X晚一天发布，学科Y早一天发布，产生A不愉悦度。
- 让学科Z早一天发布，产生B不愉悦度。
解题思路
未知的代码
三分 | 函数（洛谷P1883）
题目大意
给定n个形如\(ax^2+bx+c\)的二次函数，设\(F(x)\)为这n个函数中最大的那个，求\(F(x)\)在\([0,1000]\)中的最小值。
解题思路
三分函数值，在判断函数里，计算出所有函数在该点下的值并返回其最大值，最后得到某点满足所有函数中最大，在其他最大情况中值最小。
未知的代码
//有个数据点未过
#include<bits/stdc++.h>
using namespace std;
int main(){
int t,n;
vector<array<int,3>>param;
cin>>t;
auto calc=[&](double x){
double ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,param[i][0]*x*x+param[i][1]*x+param[i][2]);
}
return ans;
};
while(t--){
cin>>n;
param=vector<array<int,3>>(n+1);
for(int i=1;i<=n;i++)cin>>param[i][0]>>param[i][1]>>param[i][2];
double l=0,r=1e3;
for(int i=1;i<=100;i++){
double m1=l+(r-l)/3,m2=r-(r-l)/3;
if(calc(m1)>calc(m2))l=m1;
else r=m2;
}
cout<<fixed<<setprecision(4)<<calc(l)<<endl;
}
return 0;
}
Texas Trip（poj 3301）
题目大意
二维平面上有n个小孔，找出覆盖全部小点的最小正方形面积。
解题思路
在标准二维坐标系中确定x轴向最远两点，y轴向最远两点，对其在\([0,\frac{\pi}{2}]\)区间内旋转，确定满足覆盖全部孔的正方形的边长，由此产生的正方形的面积将构成一个凹函数，三分符合要求的最小边长求面积即可。
未知的代码
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
const double pi=acos(-1);
const int inf=0x3f3f3f3f;
const int N=50;
int n;
struct node{
double x,y;
}p[N];
double calc(double a){
double maxx=-inf,maxy=-inf,minx=inf,miny=inf;
for(int i=1;i<=n;i++){
maxx=max(maxx,p[i].x*cos(a)-p[i].y*sin(a));
maxy=max(maxy,p[i].x*sin(a)+p[i].y*cos(a));
minx=min(minx,p[i].x*cos(a)-p[i].y*sin(a));
miny=min(miny,p[i].x*sin(a)+p[i].y*cos(a));
}
return max(maxx-minx,maxy-miny);
}
int main(){
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
double l=0,r=pi;
for(int i=1;i<=100;i++){
double m1=l+(r-l)/3,m2=r-(r-l)/3;
if(calc(m1)>calc(m2))l=m1;
else r=m2;
}
cout<<fixed<<setprecision(2)<<pow(calc(l),2)<<endl;
}
return 0;
}
UmBasketella （poj 3737）
题目大意
给定锥体表面积，求最大体积。
解题思路
锥体表面积：\(S=\pi r+\pi rl,V=\frac{1}{3}Sh\)，体积取决于底面半径\(r\)和圆锥高\(h\)，根据\(l^2-r^2=h^2\)三分半径，求得最值.
未知的代码
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
const double pi = acos(-1);
double s, v,h,l;
double calc(double r){
l = (s - pi*r*r)/(pi*r);
h = sqrt(l*l - r*r);
v = (h*pi*r*r)/3.0;
return v;
}
int main(){
while(cin>>s){
double l=0,r=sqrt(s/pi/2);
while(r-l>1e-5){
double m1=l+(r-l)/3,m2=r-(r-l)/3;
if(calc(m1)>calc(m2))r=m2;
else l=m1;
}
cout<<fixed<<setprecision(2)<<v<<endl<<h<<endl<<r<<endl;
}
return 0;
}
Communication System（poj 1018）
题目大意
有n个设备，每个设备有mi个厂家生成，包含带宽B和价格P两个指标，B是全部所选设备的最小贷款值，P是所选所有设备价格总和，要给每个设备选出一个厂家，使B/P尽可能大。
解题思路
本体用动态规划解最优，也可枚举贪心求解。
未知的代码
#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;
const int N=105;
int b[N];
int p[N];
int dp[N][N*N];
int main(){
int t;
cin>>t;
while(t--){
int n,m;
memset(dp,-1,sizeof(dp));
cin>>n;
int maxb=0;
for(int i=1;i<=n;i++){
cin>>m;
for(int j=1;j<=m;j++){
cin>>b[j]>>p[j];
maxb=max(maxb,b[j]);
}
if(i==1){
for(int j=1;j<=m;j++)
dp[i][b[j]]=p[j];
continue;
}
for(int k=0;k<=maxb;k++){
if(dp[i-1][k]==-1)continue;
for(int j=1;j<=m;j++){
int mb=min(k,b[j]);
if(dp[i][mb]==-1)dp[i][mb]=dp[i-1][k]+p[j];
else dp[i][mb]=min(dp[i][mb],dp[i-1][k]+p[j]);
}
}
}
double ans=0;
for(int i=0;i<=maxb;i++)
ans=max(ans,(1.0*i)/dp[n][i]);
cout<<fixed<<setprecision(3)<<ans<<endl;
}
return 0;
}