2020杭电多校第三场 Triangle Collision（计算几何，坐标翻转，镜像对称）

本文主要是介绍2020杭电多校第三场 Triangle Collision（计算几何，坐标翻转，镜像对称），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
一个小球在一个等边三角形内碰撞，碰撞速度不比，方向沿边镜像翻折。求发送$k$次碰撞需要多少时间

思路：
一开始想着是模拟，然后估摸着最后会形成循环，经过起始点。但是太难模拟了。。

看了题解发现，真的特别巧妙。反射意味着穿过！那么就成了全是等边三角形铺成的平面，已知起点和速度。求经过$k$条边的最短时间。

这个时间可以二分。

仅考虑平行x轴的边，那就直接用$abs\lfloor \frac{y}{h}\rfloor$即可（-0.5向下取整是-1，同样适用）。

对于左右两条边，我们则需要将终点坐标翻转再算。
因为左右两条边一开始都不经过源点，所以我们要将终点翻转后的纵坐标向上平移$\frac{h}{2}$，使得左右边为底边，这样就和原来平行x轴的边算法一样了。（看题解的时候，这里纠结了好久┭┮﹏┭┮）

平面坐标翻转：https://blog.csdn.net/sinat_33425327/article/details/78333946

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>using namespace std;typedef long long ll;
const int maxn = 205;
const double PI = acos(-1);
const double base = 2 * PI / 3;double L,x,y,vx,vy,h;
int k;struct Point {double x,y;Point(){}Point(double x,double y) {this -> x = x;this -> y = y;}
};Point Rotate(Point a,double rad) { //坐标逆时针变换return Point(a.x * cos(rad) - (a.y) * sin(rad),a.x * sin(rad) + (a.y) * cos(rad));
}bool check(double t) {ll num = 0;Point now = Point(x + t * vx,y + t * vy);Point p1 = Rotate(now, base * 0);num += abs(floor(p1.y / h));Point p2 = Rotate(now, base * 1);p2.y += h / 2;// 以右边为平行x轴，则需向上平行h/2使得其经过源点，相当于三角形左移h/2num += abs(floor(p2.y / h));Point p3 = Rotate(now, base * 2);p3.y += h / 2;// 同上num += abs(floor(p3.y / h));return num >= k;
}int main() {int T;scanf("%d",&T);while(T--) {scanf("%lf%lf%lf%lf%lf%d",&L,&x,&y,&vx,&vy,&k);h = sqrt(3) / 2 * L;double l = 0,r = 1e11;while(r - l > 1e-6) {double mid = (l + r) / 2;if(check(mid)) {r = mid;} else {l = mid;}}printf("%.10f\n",(l + r) / 2);}return 0;
}

这篇关于2020杭电多校第三场 Triangle Collision（计算几何，坐标翻转，镜像对称）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---