2020 杭电多校第三场 H. Triangle Collision(反射套路 + 绕点旋转 + 矢量分解)

大意：给出一个等边三角形 ， 以底边中线建立坐标系 ， 给出三角形中一点 ， 和其初始速度 ， 小球在等边三角形中做完全弹性碰撞 ， 问其恰好碰撞 k 次的时间。

解法：

trick1: 反射套路

对于这样一个反射套路题 ， 如果模拟在一个三角形内模拟碰撞的话 ， 显然不现实 ，所以我们可以根据反射原理 ， 将路径变成一条直线。这样问题就变成了射线在下图中的交点个数问题。

trick2: 我们不妨先思考水平直线相交个数如何求。假设运动实现为 t 那么显然交点个数就是

$$abs(floor(\frac{y+v_{y}t}{h}))$$

对于另外两种直线 ， 我们要求相应坐标系下的 y 和 vy

对于 y(标量) 的求法有两种 ， 第一种是用点到直线的距离公式 ， 但是点到直线距离公式中有除法 ， 误差很大 ， 所以精度不够。

第二种方法是我们可以把操作转化成绕三角形中心旋转坐标系 ， 对应点的坐标也绕中心旋转后即是答案。

trick3:

对于 vy(矢量) ， 我们设立好正方向 ， 进行矢量分解即可。一定要设立正方向 ， 因为矢量是有方向的。

这样就能求得某一时刻 t 穿过点数量 ， 二分一下 t 即可。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;//--------------------------------------------------------------
const double eps = 1e-5;
const double pi = acos(-1);
inline double sqr(double x) {return x * x;} //平方
int sign(double x){if(fabs(x) < eps) return 0;if(x > 0) return 1;return -1;
}//符号
struct point{double x , y;point(){}point(double a , double b) : x(a) , y(b){}friend point operator + (const point &a , const point &b){return point(a.x + b.x , a.y + b.y);}friend point operator - (const point &a , const point &b){return point(a.x - b.x , a.y - b.y);}friend bool operator == (const point &a , const point &b){return !sign(a.x - b.x) && !sign(a.y - b.y);}friend point operator * (const point &a , const double &b){return point(a.x * b , a.y * b);}friend point operator * (const double &a , const point &b){return point(a * b.x , a * b.y);}friend point operator / (const point &a , const double &b){return point(a.x / b , a.y / b);}//向量模长 double norm(){ return sqrt(sqr(x) + sqr(y));}
}; //坐标轴绕某点旋转后 ， 原坐标轴下的点也会绕这个点旋转
double rotate_point(const point &a , const point &p , double A){double tx = p.x - a.x , ty = p.y - a.y;return a.y + tx * sin(A) + ty * cos(A);
}// p 点 绕 a 点逆时针旋转 A 弧度
//--------------------------------------------------------------int t , k;
double h , x , y , vx , vy , yr , yl;int solve(double st , double v , double t){return abs(floor((st + v * t) / h));
}bool check(double t){int res = 0;res += solve(y , vy , t);//水平res += solve(yr , (vx * sqrt(3) - vy) / 2 , t);res += solve(yl , (-vx * sqrt(3) - vy) / 2 , t);return res >= k;
}signed main(){cout << fixed << setprecision(10);cin >> t;while(t --){cin >> h >> x >> y >> vx >> vy >> k;h = h * sqrt(3) / 2;yr = rotate_point(point{0 , h / 3} , point{x , y} , pi / 3 * 2);yl = rotate_point(point{0 , h / 3} , point{x , y} , pi / 3 * 4);double l = 0 , r = 1e9 , mid = 0;while(r - l > eps){mid = (l + r) / 2;if(check(mid)) r = mid;else l = mid;}cout << mid << "\n";		}return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);