「Codeforces 724C」Ray Tracing

发表于 | | 阅读次数:
字数统计: 721 字

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%