Can’t be easierTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 632Accepted Submission(s): 275
Problem Description
I’m sure this problem will fit you as long as you didn’t sleep in your High School Math classes.Yes,it just need a little math knowledge and I know girls are always smarter than we expeted.So don’t hesitate any more,come and AC it!Tell you three point A,B,C in a 2-D plain,then a line L with a slope K pass through C,you are going to finda point P on L,that makes |AP| + |PB| minimal.
Input
The first line contain a t.Then t cases followed,each case has two parts,the first part is a real number K,indicating the slope,and the secondpart are three pairs of integers Ax,Ay,Bx,By,Cx,Cy(0 <=|Ax|,|Ay|,|Bx|,|By|,|Cx|,|Cy| <= 10000 ).
Output
Just out put the minimal |AP| + |PB|(accurate to two places of decimals ).
Sample Input
12.558467 6334 6500 9169 5724 1478
Sample Output
3450.55
Author
Teddy
Source
HDU女生专场公开赛——谁说女子不如男
这题真的是纯数学的题目。。。而且还是高中的数学。。。
直接说题意吧。。
给你一个直线的斜率K。和C点的坐标。
直线过C点。。
然后给你A,B两点的坐标，求在C点上找一点P。使得AP+PB最短。。。
Ax,Ay,Bx,By,Cx,Cy(0 <=|Ax|,|Ay|,|Bx|,|By|,|Cx|,|Cy| <= 10000 ).。。
赤裸裸的几何题啊。要是放在高中就是水题了，难得是如何用编程去表达出来。。。
首先要考虑A,B两点同侧异侧的情况 。。。
先求直线的方程。
易得：l1=kx-y-k*Cx+Cy；
然后A,B两点分别代入。
如果（k*Ax-Ay-k*Cx+Cy)*(k*Bx-By-k*Cx+Cy)>0
同侧。。
否则异侧。。
异侧的情况直接求两点距离。
同侧的话。就比较麻烦了。。
首先我以B点作直线l2垂直于直线l1。
设x1,y1为l2上B点的对称点的坐标。
设点D（x1,y1）;
易得
(y1-By)/(x1-Bx)*k=-1 ……①；
我们可以知道B,D两点的终点必然在直线l1上。
于是得到方程
(x1+Bx)/2*k-(y1+By)/2-k*Cx+Cy=0……②；
联立①②可求出
y1=(2*Bx*k+By*k*k-By-2*k*Cx+2*Cy)/(k*k+1);
x1=Bx-(y1-By)*k;
然后直接计算A,D两点的距离即为所求
OK。。
问题解决。
中间计算挺麻烦的。。
#include <stdio.h>#include <cmath>#include <vector>#include <map>#include <time.h>#include <cstring>#include <set>#include<iostream>#include <queue>#include <stack>#include <algorithm>using namespace std;#define inf 0x6f6f6f6f/*double diandaozhixiandejuli(double k,double cx,double cy,double bx,double by){return abs((k*bx-by-k*cx+cy))*1.0/(sqrt(k*k+1)); //多求了一个点到直线距离，没啥用处。。}*/double liangdianzhijiandejuli(double ax,double ay,double x1,double y1){return sqrt((ax-x1)*(ax-x1)+(ay-y1)*(ay-y1));}int main(){int t;scanf("%d",&t);while(t–){double ax,ay,bx,by,cx,cy,k,l;double x1,y1,ans;scanf("%lf",&k);scanf("%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&cx,&cy);if((k*ax-ay-k*cx+cy)*(k*bx-by-k*cx+cy)>0)//同侧{y1=(2*bx*k+by*k*k-by-2*k*cx+2*cy)/(k*k+1);x1=bx-(y1-by)*k;ans=liangdianzhijiandejuli(ax,ay,x1,y1);}else //异侧。。ans=liangdianzhijiandejuli(ax,ay,bx,by);printf("%.2lf\n",ans);}return 0;}
，穿别人的鞋，走自己的路，让别追去吧
