Collision ZOJ – 3728(计算几何计算点到直线距离 || 三分)

题目链接

https://cn.vjudge.net/problem/ZOJ-3728

题目大意

给一个以原点(0,0)为圆心,半径为Rm固定的圆饼【实心】。给一个以原点(0,0)为圆心,半径为R的大圆【空心】。有一个圆硬币,圆心为(x,y),半径为r,速度为vx,vy,硬币碰到圆饼后会以同样的能量从反射方向弹回。求硬币从进入大圆开始到离开大圆所花的时间。
可以将运动分为几种情况
1:不进大圆
2:进大圆但不碰
3:进大圆且碰撞
三种情况的判断需要用到点到线段距离的最小值。对于第一种情况,结果一定为0,而后两种情况显然是关于点到直线最近的点对称的。所以解题的关键在于求圆心到线段的距离。

解法一:计算几何

我们首先将线段看作是直线,那么当vx或vy等于零的时候,直线是平行于坐标轴的,可以直接计算,否则可以算出斜率k,用y=kx+b即kx-y+b=0来表示。然后已知计算点(x,y)到ax+by+c=0的距离为就可以解决了。

点到直线距离模板(点为源点)
double geth(){
    if(fabs(vx)<esp){
        return fabs(x);
    }
    if(fabs(vy)<esp){
        return fabs(y);
    }
    double k=vy/vx;
    double c=y-k*x;//ax+by+c=0
    double h=c/sqrt(k*k+1);
    return fabs(h);
}

三分

由于点到圆心的距离是一个单峰函数,所以可以用三分求到达据圆心最近点所需的时间,继而求出最近点的坐标。
三分代码转自:https://blog.csdn.net/gzh1992n/article/details/18667103

double getNearest(){
    double _l=0.0,_r=INF;
    int Time=1<<6;
    while(Time--){
        double L=(_l+_r)/3.0;
        double R=L*2.0;
        if(cal(L)<cal(R)) _r=R;
        else _l=L;
    }
    return (_l+_r)/2.0;
}

代码

#include <bits/stdc++.h>
const double esp=1e-6;
const int maxn = 2e3 + 100;
using namespace std;
double rm,R,r,x,y,vx,vy;
double geth(){
    if(fabs(vx)<esp){
        return fabs(x);
    }
    if(fabs(vy)<esp){
        return fabs(y);
    }
    double k=vy/vx;
    double c=y-k*x;//ax+by+c=0
    double h=c/sqrt(k*k+1);
    return fabs(h);
}
int main() {
    while(cin>>rm>>R>>r>>x>>y>>vx>>vy){
        double h=geth();
        double ans=0.0;
        double v=sqrt(vx*vx+vy*vy);
        if(x*vx+y*vy>esp){
            ans=0.0;
        }
        else if(h-R-r>esp){
            ans=0.0;
        }
        else if(h-rm-r>esp){
            ans=sqrt((R+r)*(R+r)-(h*h))*2.0/v;
        }
        else if(h-rm-r<esp){
            ans=(sqrt((R+r)*(R+r)-(h*h))-sqrt((rm+r)*(rm+r)-(h*h)))*2.0/v;
        }
        printf("%.3f\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注