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

二分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
",l);
	return 0;
}