雪色光晕（计算几何+暴力）

题目链接

https://ac.nowcoder.com/acm/contest/23479/D

题面

思路

每一秒都有一个方向向量，然后每一秒都往这个方向移动一次，那么小红和小果之间的距离就只有三种情况

• 第一种就是当前位置（没移动）到小果的距离
• 第二种就是终点位置（移动后）到小果的距离
• 第三种就是小果到这个移动线段（起点到终点）的距离 那么我们直接分三种情况去一个min就好了 关于点到线的距离博客讲解：https://blog.csdn.net/angelazy/article/details/38489293

附上出题人的讲解（非常详细）

本题要求一个固定的点到一条折线的最短距离。由于折线可以看成是很多条线段，所以可以规约成点到线段的最短距离。

（虽然这个是板子，但不建议直接去百度，毕竟赛场上没有百度）

显然，最终的答案一定为以下两种情况的一种：点到直线的最短距离、或点到线段某个端点的最短距离。

什么时候会遇到第二种情况呢？当且仅当点到直线的最短距离所对应的那个点不在线段上。

所以这道题一个最笨的方法就是：先根据线段求出直线两点式，然后求斜率乘积为-1（这样才能垂直）的直线，求出点斜式（还要特判斜率不存在的情况），这样求出两个直线交点，判断交点在不在线段上。如果在的话直接输出初始点到交点距离，否则输出初始点到线段两个端点的最小那个距离。

如果这道题用这种方法来做，计算量将非常大，题目难度也直接飙上1700+。事实上，本题有更简单的做法：

首先如何判断最终能不能取到点到直线距离呢？很简单，把点 PP 和线段两个端点 AA 和 BB ，这三个点连接成一个三角形，判断该三角形的角 AA 和角 BB 是否是钝角即可。判断钝角可以直接用勾股定理： a 2 + b 2 < c 2 a^2+b^2=1LL) { if(b & 1) ans = ans * a % mod; a = a * a % mod; } return ans; } ll lowbit(ll x){return -x & x;} const int N = 2e6+10; //----------------自定义部分---------------- int n; struct point { double x, y; }; point p1,p2,p3; double get_distance(point p, point A, point B) { point Ap, Ab, Bp; Ap.x = p.x - A.x, Ap.y = p.y - A.y; Ab.x = B.x - A.x, Ab.y = B.y - A.y; Bp.x = p.x - B.x, Bp.y = p.y - B.y; double r = (Ap.x*Ab.x + Ap.y*Ab.y)*1.0 / (Ab.x*Ab.x + Ab.y*Ab.y); if (r = 1)return sqrt(Bp.x*Bp.x*1.0+Bp.y*Bp.y); double px = A.x + Ab.x*r; double py = A.y + Ab.y*r; return sqrt((p.x-px)*(p.x-px)+(p.y-py)*(p.y-py)); } double f(point a,point b){ return sqrt(pow(a.x-b.x,2.0) + pow(a.y-b.y,2.0)); } int main() { scanf("%d",&n); scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y); double ans = f(p1,p2); while(n--){ scanf("%lf%lf",&p3.x,&p3.y); point p4 = {p1.x + p3.x,p1.y+p3.y}; ans = min(ans,f(p1,p2)); ans = min(ans,get_distance(p2,p1,p4)); p1 = p4; } printf("%.9lf\n",ans); return 0; } 标程

#include
using namespace std;
struct point{
    double x,y;
    point(double x,double y):x(x),y(y){}
};
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 ar(point A,point B,point C){ //三点三角形面积
    double a=dis(B,C),b=dis(A,C),c=dis(A,B);
    double p=(a+b+c)/2;
    return sqrt(p*(p-a)*(p-b)*(p-c));
}
int jud(point A,point B,point C){       //判断角ABC是钝角
    double a=dis(B,C),b=dis(A,C),c=dis(A,B);

    return b*b>a*a+c*c;
}
double f(point a,point b,point c){  //c点到ab线段的最小距离
    double d1=dis(a,c),d2=dis(b,c);
    if(jud(c,a,b)||jud(c,b,a))
        return min(d1,d2);
    double s=ar(a,b,c);
    double d3=2*s/dis(a,b);
    return min(min(d1,d2),d3);
}
int main(){
    int n,i,j,k;
    double x,y,x0,y0;
    cin>>n;
    cin>>x0>>y0>>x>>y;
    point purple(x,y);
    point red(x0,y0);
    double res=1e16;
    for(i=0;i>xt>>yt;
        point temp(red.x+xt,red.y+yt);
        res=min(res,f(red,temp,purple));
        red=temp;
    }
    printf("%.8f",res);
}