2020HDU多校第三场 Triangle Collision

HDU6798

http://acm.hdu.edu.cn/showproblem.php?pid=6798
参考博客 >https://www.cnblogs.com/stelayuri/p/13393651.html

大致题意：给定等边三角形的三个点，内有一动点，给定动点的速度向量，点与三角形边碰撞以镜面反射的角度改变方向，速度不变，求经过k次碰撞的时间。

分析；二分时间进行判断，碰撞可以看出无限个三角形进行拼接的二维平面，对于一个点移动形成的射线，与直线所经过的点数。(二维平面镜面碰撞问题)
预处理三种坐标系，分别是以AB,AC,BC为X坐标轴，动点的速度向量。然后根据 求交点。具体三种坐标视图.引用上述大佬博客的图。(水印抱歉

BC为X坐标轴。

当点往BC的下端移动时，计算答案时候要加上BC这条边。

AB为X坐标轴(BC同理)

当点往AB的下端移动时，计算答案时候要加上AB这条边。

#include<bits/stdc++.h>
using namespace std;


using namespace std;

typedef long long ll;
typedef double db;
const db eps=1e-6;
const db PI=acos(-1.0);
const int maxn=5e3+10;

int n;


inline db readb()
{   
    int f=1;db x=0;char s=getchar();
    for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
    for( ;isdigit(s);x=x*10+s-48,s=getchar());
    if( s=='.' ) for( db l=0.1,s=getchar();isdigit(s);x=x+(s-48)*l,l/=10,s=getchar() );
    return x*f;
}

int sgn( double d ) { return (d>eps)-(d<-eps); }; // 精度判断 


struct point{
    db x,y;
    point(){ x=y=0; }
    point(db _x,db _y ){ x=_x,y=_y; }
    point operator + ( const point &rhs ) const { return point(x+rhs.x,y+rhs.y); }
    point operator - ( const point &rhs ) const { return point(x-rhs.x,y-rhs.y); }
    point operator / ( const int &rhs ) const { return point(x/rhs,y/rhs); }
    db operator * ( const point &rhs ) const { return 1ll*x*rhs.y-1ll*y*rhs.x; } 
    db dot( const point &rhs ) const { return 1ll*x*rhs.x+1ll*y*rhs.y; }
    void get(){ x=readb(),y=readb(); }
    bool operator == ( const point &rhs ) const { return x==rhs.x && y==rhs.y; }
    bool operator < ( const point &rhs ) const { return sgn(x-rhs.x)<0 || sgn(x-rhs.x)==0 && sgn(y-rhs.y)<0 ; }
    point Rotate( db rad ) { return point(x*cos(rad)-y*sin(rad), x*sin(rad)+y*cos(rad) ); }
    // bool operator < ( const point &rhs ) const { return (*this)*rhs>0 ; } 极角排序 
};

db dist( point a,point b ) { return sqrt( (b-a).dot(b-a) ); }





//--------------------直线---------------- 
struct sLine{ // 直线 
    point s,e;
    sLine(){}
    sLine( point _s,point _e ) { s=_s,e=_e; }
    pair<point,int> operator & ( const sLine &rhs ) const{ // 两直线相交问题 
        point res=s; //交点 
        if( sgn( (s-e)*(rhs.s-rhs.e) )==0 )
        {
            if( sgn( (rhs.s-s)*(rhs.e-s) )==0 ) return make_pair(res,0); // 两直线重合
            else return make_pair( res,1 ); // 两直线平行 
        }
        db t= ( (s-rhs.s)*(rhs.s-rhs.e) )/ ( (s-e)*(rhs.s-rhs.e) ) ; //单位化 
        res.x+=(e.x-s.x)*t;
        res.y+=(e.y-s.y)*t;
        return make_pair(res,2); // 有交点 
    }

    db getDistance( point A ) //点到直线的距离
    { 
        return fabs((A-s)*(A-e)/dist(s,e) );
    }
};



db L,x,y,vx,vy,h;
int k;
point A,B,C,oripot,v1,v2,v3;
sLine AB,AC,BC; 


bool check( db tim )
{
    ll res=0;
    db dis;
    dis=BC.getDistance(oripot)+v1.y*tim;  //第一种坐标系对应边BC，计算出起点高度+y轴经过距离Δy
    if( dis<0 ) res+=(ll)(-dis/h)+1;      //如果方向为负方向，计算结果与直接整除略有不同
    else res+=(ll)(dis/h);                //正方向正常整除

    dis=AC.getDistance(oripot)+v2.y*tim;  //第一种坐标系对应边AC，计算出起点高度+y轴经过距离Δy
    if( dis<0 ) res+=(ll)(-dis/h)+1;
    else res+=(ll)(dis/h);

    dis=AB.getDistance(oripot)+v3.y*tim; //第一种坐标系对应边AB，计算出起点高度+y轴经过距离Δy
    if( dis<0 ) res+=(ll)(-dis/h)+1;
    else res+=(ll)(dis/h);

    return res>=k ;                          //最后判断当前的交点个数是否大于等于要求的个数
} 


void solve()
{
    L=readb(),x=readb(),y=readb(),vx=readb(),vy=readb(),k=readb();
    h=sqrt(3)*L/2.0;  //三角形高度

    v1=point(vx,vy);  //第一种坐标系下的速度向量
    v2=v1.Rotate(PI*2.0/3);  //第二种坐标系下的速度向量（逆时针旋转120°）
    v3=v1.Rotate(-PI*2.0/3); //第三种坐标系下的速度向量（顺时针旋转120°）

    oripot=point(x,y);   // 初始点位置 
    A=point(0,h);
    B=point(L/2.0,0);
    C=point(-L/2.0,0);

    AB=sLine(A,B);
    AC=sLine(A,C);
    BC=sLine(B,C);

    db l=0,r=1e10,mid;
    while( r-l>=1e-6 )
    {
        mid=(l+r)/2.0;
        if( check(mid) ) r=mid;
        else l=mid;
    }
    printf("%lf\n",r);
}

int main()
{
    int T=readb();
    while( T-- ) solve();
    return 0;
}