「Codeforces 724C」Ray Tracing

Description

题目链接:Codeforces 724C

有一个 $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_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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}
0%