HDU多校3 - 6798 Triangle Collision(几何+旋转坐标系)

题目链接：点击查看

题目大意：给出一个等边三角形的区域，再给出初始时一个质点的位置 ( x , y ) 和初始速度 ( vx , vy ) ，现在质点会不断运动，当碰到三角形的内壁时会根据角度反弹，问小球第 k 次碰到三角形的内壁的时间

题目分析：k 非常大，肯定不能暴力去模拟每一次小球的运动，借用题解的一句话更好理解：

灵感来自用激光笔往镜子中射入激光被多次反射。
人眼从激光笔的视角来看，光束并没有被 “反射”，而是穿入了 “镜子中的世界”。

将二维平面视为无穷大，大概就是这样互相拼接而成的等边三角形假设点 A 为起点，点 B 为一段时间后到达的位置，则线段 AB 穿过的三角形的边数，就是质点碰撞三角形内壁的次数了

这样一来，可以二分时间，然后去检查线段穿过的次数与题目中给出 k 的关系，当然，计算穿过的边数也是有技巧的，如果硬算投影的话应该也是可以的，只是比较麻烦，首先考虑如果只是计算穿过的蓝色线段的数量，可以直接根据 y 的值稍加计算得到，同理，可以旋转一下坐标系，这样就能很方便的求出穿过黄色和红色直线的条数了

借用一下大佬博客的图片：https://blog.csdn.net/jk_chen_acmer/article/details/107641065

像上面一样，每次逆时针旋转 120 度即可

注意一下，因为我们在旋转后，想要使得初始的三角形的三条边位于 x 轴上，所以初始点 P 是围绕着三角形的中心旋转的，而速度向量是 V - O 构成的，换句话说，需要将点 V 和点 O 分别旋转后再做减法得到向量（这样操做或许比较麻烦，但个人看来是最容易理解的）

因为在进行上述旋转后，有一个好处就是，初始时的点 P 的 y 坐标一定是大于 0 的，所以此时对于运动停止时的点 Q ，我们分两种情况讨论：

Q.y > 0：Q 和 P 位于 x 轴的同一侧，此时答案为

Q.y < 0：Q 和 P 位于 x 轴的不同侧，需要加上 y = 0 这条直线，此时答案为（因为 Q.y 是小于 0 的，所以需要减）

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;const double eps = 1e-8;const double pi = acos(-1.0);int sgn(double x){if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1; }struct Point{double x,y;Point(){}Point(double _x,double _y){x = _x;y = _y;}bool operator == (Point b)const{return sgn(y-b.y) == 0;}bool operator < (Point b)const{return sgn(y-b.y)<0;}Point operator -(const Point &b)const{return Point(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{return Point(x*k,y*k);}//叉积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;}//返回两点的距离double distance(Point p){return hypot(x-p.x,y-p.y);}//`绕着p点逆时针旋转angle`Point rotate(Point p,double angle){Point v = (*this) - p;double c = cos(angle), s = sin(angle);return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);} };double L,x,y,vx,vy,h;int k;Point P[4],Q[4],V[4],O[4],T;LL cal(double t,int i) {Point Q=P[i]+V[i]*t;if(sgn(Q.y)>=0)return (LL)floor(Q.y/h);elsereturn 1LL-(LL)ceil(Q.y/h); }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%lf%lf%lf%lf%lf%d",&L,&x,&y,&vx,&vy,&k);h=sqrt(3)*L/2.0;T=Point(0,h/3.0);//中心点O[1]=Point(0,0),O[2]=O[1].rotate(T,pi*2.0/3.0),O[3]=O[1].rotate(T,pi*4.0/3.0);//原点P[1]=Point(x,y),P[2]=P[1].rotate(T,pi*2.0/3.0),P[3]=P[1].rotate(T,pi*4.0/3.0);//初始点V[1]=Point(vx,vy),V[2]=V[1].rotate(T,pi*2.0/3.0),V[3]=V[1].rotate(T,pi*4.0/3.0);//速度向量for(int i=1;i<=3;i++)V[i]=V[i]-O[i];//得到速度向量double l=0,r=1e10,ans;while(fabs(l-r)>=1e-5){double mid=(l+r)*0.5;if(cal(mid,1)+cal(mid,2)+cal(mid,3)>=k){ans=mid;r=mid;}elsel=mid;}printf("%.10f\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU多校3 - 6798 Triangle Collision(几何+旋转坐标系)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。