首页 > ACM题库 > HDU-杭电 > HDU 3400-Line belt -分治-[解题报告]HOJ
2014
03-23

HDU 3400-Line belt -分治-[解题报告]HOJ

Line belt

问题描述 :

In a two-dimensional plane there are two line belts, there are two segments AB and CD, lxhgww’s speed on AB is P and on CD is Q, he can move with the speed R on other area on the plane.
How long must he take to travel from A to D?

输入:

The first line is the case number T.
For each case, there are three lines.
The first line, four integers, the coordinates of A and B: Ax Ay Bx By.
The second line , four integers, the coordinates of C and D:Cx Cy Dx Dy.
The third line, three integers, P Q R.
0<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

输出:

The first line is the case number T.
For each case, there are three lines.
The first line, four integers, the coordinates of A and B: Ax Ay Bx By.
The second line , four integers, the coordinates of C and D:Cx Cy Dx Dy.
The third line, three integers, P Q R.
0<= Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

样例输入:

1
0 0 0 100
100 0 100 100
2 2 1

样例输出:

136.60

 

题目大意:

给出两条平行的线段AB, CD,然后一个人在线段AB的A点出发,走向D点,其中,人在线段AB上的速度为P, 在线段CD上的速度为Q,在其他地方的速度为R,求人从A点到D点的最短时间。

 

————————————————————————————-

解题思路:

一开始看到这个题,就知道是数学题,但是没有找到合适的数学模型。。后来看了大牛的解题报告,提到了三分,才突然想到,这个题应该是化为函数,求函数的极值。由于之前没听过三分,所以花了一晚的时间研究了一下三分。。做了几个简单题垫垫底,这个题终于一A了~痛快~~(*^__^*) 嘻嘻……

 

额。。。。跑题了。。

 

说说这个题怎么做…

Line belt

如上图所示,红线部分为人走的路径。人所用的时间为 T = X / P + Y / Q + Z / R。

然后我们做一个变形,令人在线段AB上花的时间为:F(X) = X / P ,假设X是一个确定值的前提下,人走完Z和Y所花的时间为:G(Y) = Z / R + Y / Q。当X 和Y都确定的情况下,Z也是一个确定值。所以,所求的函数可以写成: T(X,Y) = F(X) + G(Y)。因为T是一个关于X和Y的函数,而G只是一个关于Y的函数,所以,可以用两层嵌套的三分法解这个方程。首先以X为变量,对T进行三分。在求G的值的时候,以Y为变量,对G进行三分,求出G在对应的X下的最小值。这样就能求出T的最小值了。

如何证明这个题能够用三分解?

首先,F(X)函数是一个单调递增的函数,而G(Y)很明显是一个先递减后递增的函数。两个函数叠加,所得的T(X,Y)函数应该也是一个先递减后递增的函数。故可用三分法解之。

 

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct point
{
	double x,y;
};
const double eps=1e-4;
double p,q,r;
double dis(point a,point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double cal_ab(point a,point b,point m)
{
	point left=a,right=b;
	point mid,midmid;
	double ans1,ans2;
	do
	{
		mid.x=(left.x+right.x)/2.0;
		mid.y=(left.y+right.y)/2.0;
		midmid.x=(left.x+mid.x)/2.0;
		midmid.y=(left.y+mid.y)/2.0;
		ans1=dis(mid,a)/p+dis(mid,m)/r;
		ans2=dis(midmid,a)/p+dis(midmid,m)/r;
		if(ans1<ans2)
			left=midmid;
		else
			right=mid;
	}while(fabs(ans1-ans2)>eps);
	return ans1;
}
double cal_abcd(point a,point b,point c,point d)
{
	point left=c,right=d;
	point m,mm;
	double ans1,ans2;
	do
	{
		m.x=(left.x+right.x)/2.0;
		m.y=(left.y+right.y)/2.0;
		mm.x=(left.x+m.x)/2.0;
		mm.y=(left.y+m.y)/2.0;
		ans1=dis(m,d)/q+cal_ab(a,b,m);
		ans2=dis(mm,d)/q+cal_ab(a,b,mm);
		if(ans1<ans2)
			left=mm;          //做三分题时的一句口诀:小(left)对小,大(right)对大
		else
			right=m;
	}while(fabs(ans1-ans2)>eps);
	return ans1;
}
int main()
{
	int t;
	point a,b,c,d;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
		scanf("%lf%lf%lf",&p,&q,&r);
		printf("%.2lf/n",cal_abcd(a,b,c,d));
	}
	return 0;
}

参考:http://blog.csdn.net/scnujack/article/details/6277534


  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  4. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  5. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。