bzoj 1857 三分套三分

题目大意

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。lxhgww在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在lxhgww想从A点走到D点，他想知道最少需要走多长时间

分析

路线是A-线段-X-平面-Y-线段-D

可以发现两边都是单峰函数

证明不会（我连导都不会求）挖坑

做法

三分AB中一点，再三分CD中一点

姿势

用结构体pt存，写起来就跟正常的浮点数三分一毛一样

solution

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

typedef double db;

using namespace std;

const db eps=1e-7;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

struct pt{

	db x,y;

	pt(db _x=0.0,db _y=0.0){x=_x;y=_y;}

};

pt operator +(pt x, pt y){return pt(x.x+y.x,x.y+y.y);}

pt operator -(pt x, pt y){return pt(x.x-y.x,x.y-y.y);}

pt operator *(pt x, db d){return pt(x.x*d,x.y*d);}

pt operator /(pt x, db d){return pt(x.x/d,x.y/d);}

db dot(pt x,pt y){return x.x*y.x+x.y*y.y;}

db cross(pt x,pt y){return x.x*y.y-x.y*y.x;}

db length(pt x){return sqrt(dot(x,x));}

db dis(pt x,pt y){return length(y-x);}

pt A,B,C,D;

db P,Q,R;

db calc(pt x){

	pt l=C,r=D,m1,m2;

	db tp1,tp2;

	while(dis(l,r)>eps){

		m1=(l+l+r)/3.0;

		m2=(r+l+r)/3.0;

		tp1=dis(m1,D)/Q+dis(x,m1)/R;

		tp2=dis(m2,D)/Q+dis(x,m2)/R;

		if(tp1<tp2) r=m2;

		else l=m1;

	}

	tp1=dis(l,D)/Q+dis(x,l)/R;

	tp2=dis(r,D)/Q+dis(x,r)/R;

	return min(tp1,tp2);

}

int main(){

	#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	#endif

	int x,y;

	x=rd(),y=rd(); A=pt(x,y);

	x=rd(),y=rd(); B=pt(x,y);

	x=rd(),y=rd(); C=pt(x,y);

	x=rd(),y=rd(); D=pt(x,y);

	x=rd(); P=x;

	x=rd(); Q=x;

	x=rd(); R=x;

	pt l=A,r=B,m1,m2;

	db tp1,tp2;

	while(dis(l,r)>eps){

		m1=(l+l+r)/3.0;

		m2=(r+l+r)/3.0;

		tp1=calc(m1)+dis(A,m1)/P;

		tp2=calc(m2)+dis(A,m2)/P;

		if(tp1<tp2) r=m2;

		else l=m1;

	}

	tp1=calc(l)+dis(A,l)/P;

	tp2=calc(r)+dis(A,r)/P;

	printf("%.2lf",min(tp1,tp2));

	return 0;

}

巴特西

bzoj 1857 三分套三分

题目大意

分析

做法

姿势

solution

最新文章

热门文章