[SCOI2010]传送带

三分法模板。

关于为什么可以三分，我选择感性理解，有人证明了，总之我是懒得证了。

假设路径是\(A \to E \to F \to D\)，\(E\)和\(F\)分别是从\(AB\)到平面上的拐角和从平面上到\(CD\)上的拐角。首先三分\(E\)的位置，在此基础上三分\(F\)的位置就可以了。

#include<cstdio>

#include<cmath>

#define I inline

#define D double

using namespace std;

const D eps=1e-6;

struct N{D x,y;}a,b,c,d;

D P,Q,R;

I D pwr(D x){return x*x;}

I D dst(N a,N b){return sqrt(pwr(a.x-b.x)+pwr(a.y-b.y));}

D dac0(N f){

	N l=c,r=d,p,q;

	D u,v,o,e;

	while(dst(l,r)>eps)

		u=(r.x-l.x)/3,v=(r.y-l.y)/3,p=(N){l.x+u,l.y+v},q=(N){r.x-u,r.y-v},o=dst(f,p)/R+dst(p,d)/Q,e=dst(f,q)/R+dst(q,d)/Q,e-o>eps?r=q:l=p;

	return dst(f,l)/R+dst(l,d)/Q;

}

D dac(){

	N l=a,r=b,p,q;

	D u,v,o,e;

	while(dst(l,r)>eps)

		u=(r.x-l.x)/3,v=(r.y-l.y)/3,p=(N){l.x+u,l.y+v},q=(N){r.x-u,r.y-v},o=dst(a,p)/P+dac0(p),e=dst(a,q)/P+dac0(q),e-o>eps?r=q:l=p;

	return dac0(l)+dst(a,l)/P;

}

int main(){

	scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y,&P,&Q,&R);

	printf("%.2lf",dac());

	return 0;

}

巴特西

[SCOI2010]传送带三分法

[SCOI2010]传送带

最新文章

热门文章

巴特西

[SCOI2010]传送带 三分法

[SCOI2010]传送带

最新文章

热门文章

[SCOI2010]传送带三分法