HDU - 2671(计算几何)

妖狐艹你老母 2022-06-09 09:50 213阅读 0赞

问题描述:

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.

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 second   
part 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

1
    2.55
    8467 6334 6500 9169 5724 1478

Sample Output

3450.55

问题描述:题目给我们一个斜率K，三个点(A,B,C)的坐标，让我们在一条直线(斜率为K,过C点),找到一点P使得|AP|+|BP|最小。

题目分析:我们先求出直线L的方程，然后根据直线方程来判断A与B是否同侧(判断方法就是：将点A,B代入直线方程中算它们的结果的积如果小于0，异测，等于0，至少有一点在直线上，大于0，同侧，判断原理就是：点在直线上方结果大于0，下方小于0，中等于0）;

如果异侧：则直接求A与B的距离

如果同侧：则求出A点（B点也可）关于直线L对称的点D，求出B与D 的距离。（求D点时，可以先求出B与D的中点mid（联立方程即可))

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    
    struct Point
    {
        double x,y;
    };
    
    double get_dis(Point a,Point b)
    {
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--) {
            double k;
            Point a,b,c;
            scanf("%lf",&k);
            scanf("%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
            double A=k*a.x+c.y-k*c.x-a.y;
            double B=k*b.x+c.y-k*c.x-b.y;
            if (A*B<=0) {
                printf("%.2f\n",get_dis(a,b));
            }
            else {
                if (k==0) {//当k等于0的时候，中点公式
                    Point d;
                    d.x=a.x;
                    d.y=2*c.y-a.y;
                    printf("%.2f\n",get_dis(b,d));
                }
                else {
                    double k1,k2,b1,b2;
                    Point mid,d;
                    k1=k,k2=-1.0/k;
                    b1=c.y-k*c.x;
                    b2=a.y+a.x/k;
                    mid.x=(b2-b1)/(k1-k2);//中点
                    mid.y=k2*mid.x+b2;
                    d.x=2*mid.x-a.x;
                    d.y=2*mid.y-a.y;
                    printf("%.2f\n",get_dis(b,d));
                }
            }
        }
        return 0;
    }