【二分】Urozero Autumn Training Camp 2016 Day 5: NWERC-2016 Problem C. Careful Ascent

时间:2025-04-12 22:35:31

二分Vx即可。

#include<cstdio>
#include<algorithm>
using namespace std;
#define EPS 0.00000000001
struct RANGE{
int l,r;
double f;
}rs[110];
bool cmp(const RANGE &a,const RANGE &b){
return a.l<b.l;
}
int xe,ye,n,Left;
bool check(double vx){
double sumx=0;
for(int i=1;i<=n;++i){
sumx+=(double)(rs[i].r-rs[i].l)*vx*rs[i].f;
}
return sumx+(double)Left*vx-(double)xe > -EPS;
}
int main(){
// freopen("c.in","r",stdin);
scanf("%d%d%d",&xe,&ye,&n);
Left=ye;
for(int i=1;i<=n;++i){
scanf("%d%d%lf",&rs[i].l,&rs[i].r,&rs[i].f);
Left-=(rs[i].r-rs[i].l);
}
sort(rs+1,rs+n+1,cmp);
double l=-10000000,r=10000000;
while(r-l>EPS){
double mid=(l+r)/2.0;
if(check(mid)){
r=mid;
}
else{
l=mid+EPS;
}
}
printf("%.11f\n",l);
return 0;
}