题解 CF724C 【Ray Tracing】
Siyuan
2019-02-08 10:53:14
[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-Codeforces-724C-Ray-Tracing/)
---
## Description
> 题目链接：[Codeforces 724C](https://codeforces.com/contest/724/problem/C)
有一个 $n\times m$ 的矩形，四周有围墙围起来，其左上角和右下角的坐标分别为 $(0,0)$ 和 $(n,m)$。从 $(0,0)$ 开始以 $\sqrt 2$ 个单位每秒的速度向 $(1,1)$ 的方向发射一束光线，每次遇到墙都正常反射（符合物理的反射），光线射到顶点会被吸收。在这个矩形内有 $k$ 个点，坐标分别为 $(x_i,y_i)$，求每个点第一次被光线经过的时刻。
数据范围：$2\le n,m\le 10^5$，$1\le k\le 10^5$，$1\le x_i<n$，$1\le y_i<m$
------
## Solution
对于这类矩形内上的反射问题，我们可以将矩形**无限展开**，那么相当于我们把点按照矩形边界**对称**，光线也就边成了**一条直线**。
我们考虑对称后的点的坐标是什么。如果原来的坐标为 $(x,y)$，那么按照第 $k$ 条横轴展开的坐标为 $(x,2km-y)$，按照第 $k$ 条纵轴展开的左边为 $(kn-x,y)$。因此，如果我们沿着若干条轴展开后，坐标一定可以写成 $(k_1n\pm x,k_2m\pm y)$ 的形式。
由于我们知道了展开后的坐标，那么有如下方程：
$$k_1n\pm x=k_2m\pm y\Longrightarrow k_1n-k_2m=\pm x\pm y$$
发现这是一个**丢番图方程**，我们可以直接解出 $(k_1,k_2)$ 的通解。
但是，题目中规定光线在矩形顶点位置会被吸收，那么我们就要保证**坐标的绝对值小于等于 $\operatorname{lcm}(n,m)$**，否则光线一定会经过 $\operatorname{lcm}(n,m)$ 这个点而被吸收。
因此，我们对 $4$ 种情况分别求解，找到一组解使得 $k_1n\pm x$ 的值尽量小且大于 $0$。形象地说，就是使得 $k_1n\pm x$ 最小并满足 $0<k_1n\pm x<\operatorname{lcm}(n,m)$。
这个最小的符合条件的解就是答案。
**时间复杂度**：$O(k\log n)$
------
## Code
```cpp
#include <cstdio>
#include <algorithm>
typedef long long LL;
const LL INF=1LL<<60;
int n,m,k;
LL mx;
int gcd(int a,int b) {
return b?gcd(b,a%b):a;
}
int exgcd(int a,int b,int &x,int &y) {
if(!b) {x=1,y=0;return a;}
int d=exgcd(b,a%b,y,x);
y-=a/b*x; return d;
}
LL solve(int dx,int dy) {
int a=2*n,b=-2*m,c=dy-dx,x,y;
int d=exgcd(a,b,x,y);
if(c%d) return INF;
a/=d,b/=d,c/=d,b=std::abs(b),x=(x*c%b+b)%b;
LL ans=2LL*n*x+dx;
if(ans<=0||ans>=mx) return INF;
return ans;
}
int main() {
scanf("%d%d%d",&n,&m,&k);
mx=1LL*n*m/gcd(n,m);
while(k--) {
int x0,y0;
scanf("%d%d",&x0,&y0);
LL ans=INF;
ans=std::min(ans,solve(+x0,+y0));
ans=std::min(ans,solve(+x0,-y0));
ans=std::min(ans,solve(-x0,+y0));
ans=std::min(ans,solve(-x0,-y0));
printf("%lld\n",ans==INF?-1:ans);
}
return 0;
}
```