Triangle Collision(详解)
2020 Multi-University Training Contest 3 H / HDU 6798 - Triangle Collision
知识点: 1.计算几何。2.二分。3.问题转化。
问题分析： 由于小球在与墙壁碰撞时满足反射定律，入射角等于反射角，我们尝试是否可以用翻折的思想来解决这个问题。
1.首先画出初始的三角形
2.画出▲ABC以边AB为轴的翻折图形(▲ABC’)
3.若小球初始的坐标为P(x,y)，初始速度矢量为V ,从图中可以看出小球的两次碰撞，第一次与AB边碰撞，第二次与AC边碰撞。现在我们画出▲ABC以边AB为轴的翻折，我们会发现第一次碰撞后到第二次碰撞的轨迹与从初始位置到第一次碰撞时的轨迹在一条直线上。如果要继续分析第三次碰撞的话，我们只对▲ABC’进行分析。
(注意：光线在密闭的物体中无限反射，与这个密闭的物体本身的位置，速度都没有任何关系)
4.总之一句话：小球与哪条边碰撞了就将三角形以那条边为轴进行翻折。
5.进行了上述的转化后，小球的碰撞的次数等于穿过直线的条数，其中计算水平的直线最好算它就等于
余下的两条斜的直线我们可以将坐标系顺时针旋转120°或逆时针旋转120°度。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps=1e-8;
const double pi=acos(-1);
int dcmp(double x){
if(fabs(x)<eps) return 0;
else return x<0?-1:1;
}
struct Point{ //定义在向量上的各种操作
double x,y;
Point(){}
Point(double _x,double _y){
x=_x;
y=_y;
}
bool operator ==(Point b)const{
return dcmp(x-b.x)==0&&dcmp(y-b.y)==0;
}
Point operator -(const Point &b)const{ //两向量相减
return Point(x-b.x,y-b.y);
}
double operator ^(const Point &b)const{ //向量叉乘
return x*b.y-y*b.x;
}
double operator *(const Point &b)const{ //向量点乘
return x*b.x+y*b.y;
}
Point operator +(const Point &b)const{ //两向量相加
return Point(x+b.x,y+b.y);
}
Point operator *(const double &k)const{ //向量乘一个常数 K
return Point(x*k,y*k);
}
Point operator /(const double &k)const{ //向量除一个常数 K
return Point(x/k,y/k);
}
double distance(Point p){ //两向量间的距离
return hypot(x-p.x,y-p.y);
}
Point Ratate(double rad){ //向量逆时针旋转rad弧度后的坐标
return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));
}
};
struct Line{
Point s,e;
Line(){}
Line(Point _s,Point _e){
s=_s;
e=_e;
}
bool pointonseg(Point p){ //判断点P是否在线段上
return dcmp((p-s)^(e-s))==0&&((p-s)*(e-s))<=0;
}
double getDistance(Point A){ //点到直线的距离
return fabs((A-s)^(e-s))/s.distance(e);
}
Point crosspoint(Line v){ //求两直线的交点
double a1=(v.e-v.s)^(s-v.s);
double a2=(v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
}
};
double L,x,y,vx,vy,h;
Point A,B,C,Star,v1,v2,v3;
Line AB,AC,BC;
ll k;
ll num(double dy){ //计算穿过的直线条数
ll cnt=0;
if(dy>=0)
cnt+=(ll)(dy/h);
else
cnt+=(ll)(-dy/h)+1;
return cnt;
}
bool check(double t){
ll ans=0;
double dy;
dy=BC.getDistance(Star)+v1.y*t;
ans+=num(dy);
dy=AC.getDistance(Star)+v2.y*t;
ans+=num(dy);
dy=AB.getDistance(Star)+v3.y*t;
ans+=num(dy);
return ans>=k;
}
void Init(){
h=L*sqrt(3.0)/2.0; //三角形的高度
v1=Point(vx,vy); //初始速度向量
v2=v1.Ratate(2.0*pi/3.0);//逆时针旋转 120°后的
v3=v1.Ratate(-2.0*pi/3.0);//顺时针旋转 120°后的
Star=Point(x,y); // 初始位置向量
A=Point(0,h);
B=Point(L/2.0,0);
C=Point(-L/2.0,0);
AB=Line(A,B);
AC=Line(A,C);
BC=Line(B,C);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%lf %lf %lf %lf %lf %lld",&L,&x,&y,&vx,&vy,&k);
Init();
double l=0.0,r=1e10,mid;
while((r-l)>=1e-4){
mid=(r+l)/2.0;
if(check(mid)){
r=mid;
}
else l=mid;
}
printf("%.10f\n",mid);
}
return 0;
}