首页 > ACM题库 > HDU-杭电 > hdu 2671 Can’t be easier[解题报告]C++
2014
02-12

hdu 2671 Can’t be easier[解题报告]C++

Can’t be easier

问题描述 :

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 find
a point P on L,that makes |AP| + |PB| minimal.

输入:

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 second
part are three pairs of integers Ax,Ay,Bx,By,Cx,Cy(0 <=|Ax|,|Ay|,|Bx|,|By|,|Cx|,|Cy| <= 10000 ).

输出:

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 second
part are three pairs of integers Ax,Ay,Bx,By,Cx,Cy(0 <=|Ax|,|Ay|,|Bx|,|By|,|Cx|,|Cy| <= 10000 ).

样例输入:

1
2.55
8467 6334 6500 9169 5724 1478

样例输出:

3450.55

/*
*  题目所求:在直线上找一点P,使其与其它(A,B)两点组成的距离最短 
*  点A跟点B与直线的位置情况四种:
*  1.两点在直线的同侧(两点都不在直线上) 
*  2.两点在直线的异侧(两点都不在直线上) 
*  3.其中一点在直线上
*  4.两点都在直线上
*  auther:Try86 
*/

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

struct point {//点结构 
    double x;
    double y;
}A, B, C;

struct segment {//线段结构 
    point s;
    point e;
}seg;

struct line {//直线结构,标准式 
    double a;
    double b;
    double c;
}l;

double k;

double dis(point A, point B) {
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

int segXLine(line l, segment seg) {//判断线段是否跟直线相交 
    if ((l.a*seg.s.x+l.b*seg.s.y+l.c)*(l.a*seg.e.x+l.b*seg.e.y+l.c)<=0) return 1;
    return 0;
}

double solve() {
    point D;
    double ans = 0; 
    l.a = k;     //直线标准式 
    l.b = -1;
    l.c = C.y - k * C.x;
    seg.s = A;  //线段 
    seg.e = B;
    if (segXLine(l, seg)) ans = dis(A, B);//相交,则直接求两点距离即可 
    else {
        D.x = ((l.b*l.b-l.a*l.a)*A.x - 2*l.a*l.b*A.y - 2*l.a*l.c) / (l.a*l.a+l.b*l.b);//求点A关于直线的对称点 
        D.y = ((l.a*l.a-l.b*l.b)*A.y - 2*l.a*l.b*A.x - 2*l.b*l.c) / (l.a*l.a+l.b*l.b);
        ans = dis(B, D);//所求 
    }
    return ans;
}
 
int main() {
    int t;
    scanf ("%d", &t);
    while (t--) {
        scanf ("%lf", &k);
        scanf ("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y);
        double ans = solve();
        printf ("%.2lf\n", ans);
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/try86/archive/2012/04/22/2464683.html


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

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