代码
``` cpp
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=15;
const float eps=1e-2;
int n,tot,a[N];
float ans=1e18,r1[N],r2[N],h[N],tmp[N];
bool same(float a,float b){
return fabs(a-b)<eps;
}
bool in(float x,float l,float r){
if(l>r){
swap(l,r);
}
return x>l-eps&&x<r+eps;
}
bool eq(float xl,float yl,float xr,float yr){
return same(xl,xr)&&same(yl,yr);
}
bool check(float xa,float ya,float xb,float yb,float xc,float yc,float xd,float yd){
float k1=(ya-yb)/(xa-xb),k2=(yc-yd)/(xc-xd),b1=ya-k1*xa,b2=yc-k2*xc;
if(same(k1,k2)){
return true;
}
float x=(b2-b1)/(k1-k2),y=k1*x+b1;
if(!in(x,xa,xb)||!in(y,ya,yb)||!in(x,xc,xd)||!in(y,yc,yd)){
return true;
}
if(!eq(x,y,xa,ya)&&!eq(x,y,xb,yb)&&!eq(x,y,xc,yc)&&!eq(x,y,xd,yd)){
return false;
}
return true;
}
float calc(){
float res=h[a[1]],maxn=h[a[1]];
memset(tmp,0,sizeof(tmp));
for(int i=2;i<=n;i++){
int x=a[i-1],y=a[i];
float l,r=maxn,mid,k1,b1;
k1=h[x]/(r1[x]-r2[x]);
b1=h[x]-k1*(r1[x]-r2[x]);
if(r1[y]<=r1[x]){
l=0;
}else{
l=k1*(r1[x]-r1[y])+b1;
}
while(r-l>0.1){
mid=(l+r)/2;
bool flag=true;
for(int j=1;j<i;j++){
if(!check(0,0,r1[a[j]]-r2[a[j]],h[a[j]],r1[a[j]]-r1[y],mid+tmp[j],r1[a[j]]-r2[y],mid+tmp[j]+h[y])){
flag=false;
break;
}
}
if(flag){
r=mid;
}else{
l=mid;
}
}
for(int j=1;j<i;j++){
tmp[j]+=(l+r)/2;
}
maxn=max(maxn,h[a[i]]);
res=max(res,tmp[1]+h[a[i]]);
if(res>ans){
return res;
}
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%f%f%f",&h[i],&r1[i],&r2[i]);
a[i]=i;
}
do{
tot++;
ans=min(ans,calc());
}while(next_permutation(a+1,a+n+1));
printf("%d\n",int(ans+0.5));
return 0;
}
```
by 2016gdgzoi471 @ 2018-09-19 17:27:12
~~貌似并不是精度的问题~~
by 2016gdgzoi471 @ 2018-09-19 17:28:00
@[2016gdgzoi471](/space/show?uid=52559) STM刚学OI
by ezoixx130 @ 2018-09-20 09:24:45
@[2016gdgzoi471](/space/show?uid=52559) STM刚学OI
by ezoixx118 @ 2019-07-18 09:30:34
@[ezoixx118](/space/show?uid=30541) 挖坟了awa
by 2016gdgzoi471 @ 2019-07-30 19:18:39
@[2016gdgzoi471](/space/show?uid=52559) 你谷不算挖坟
by ezoixx118 @ 2019-07-31 11:52:44