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);
else
return 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;
}
else
l=mid;
}
printf("%.10f\n",ans);
}
return 0;
}