http://codeforces.com/contest/724/problem/C
题目大意：
在一个n*m的盒子里,从(0,0)射出一条每秒位移为(1,1)的射线,遵从反射定律,给出k个点,求射线分别第一次经过这些点的时间。
解法一： (模拟)
射线不管怎么反射,都是和水平方向成45°角的,也就是说每一段射线上的点,横坐标和纵坐标的和或者差相等。 把每一个点放入它所对应的对角线里,然后模拟射线的路径就好。
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <set>
#include <queue>
using namespace std; #define X first
#define Y second
#define Mod 1000000007
#define N 100110
#define M 200110
typedef long long ll;
typedef pair<int,int> pii; const ll INF=1e18;
int n,m,k;
ll ans[N];
pii p[N];
vector<int> dig1[N<<],dig2[N<<]; int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout); scanf("%d%d%d",&n,&m,&k);
for (int i=;i<k;i++)
{
scanf("%d%d",&p[i].X,&p[i].Y);
dig1[p[i].X-p[i].Y+N].push_back(i);
dig2[p[i].X+p[i].Y].push_back(i);
ans[i]=INF;
} int x=,y=,d,tx,lx,op=; ll t=;
do
{
lx=x;
if (x==)
{
if (op) d=min(n,m-y),x+=d,y+=d;
else d=min(n,y),x+=d,y-=d;
}
else if (x==n)
{
if (op) d=min(n,y),x-=d,y-=d;
else d=min(n,m-y),x-=d,y+=d;
}
else if (y==)
{
if (op) d=min(m,n-x),x+=d,y+=d;
else d=min(m,x),x-=d,y+=d;
}
else
{
if (op) d=min(m,x),x-=d,y-=d;
else d=min(m,n-x),x+=d,y-=d;
}
if (op)
{
for (int i=;i<dig1[x-y+N].size();i++)
{
tx=p[dig1[x-y+N][i]].X;
ans[dig1[x-y+N][i]]=min(ans[dig1[x-y+N][i]],t+abs(tx-lx));
}
}
else
{
for (int i=;i<dig2[x+y].size();i++)
{
tx=p[dig2[x+y][i]].X;
ans[dig2[x+y][i]]=min(ans[dig2[x+y][i]],t+abs(tx-lx));
}
}
t+=d,op^=;
//cout<<x<<" "<<y<<endl;
}while (!((x== && y==) || (x== && y==m) || (x==n && y==) || (x==n && y==m))); for (int i=;i<k;i++) printf("%I64d\n",ans[i]==INF? -:ans[i]);
return ;
}
解法二：(扩展欧几里得)
水平方向和竖直方向位移可以先分开考虑。
对于水平方向,每秒+1,然后n秒后,碰到墙壁,反弹,然后每秒-1,n秒后再次碰壁,又变成每秒+1.依次类推以2n为周期。
假设横坐标要从0变成x,那么只可能两种情况:
$t \equiv\ x\ (mod\ 2n)$
$t \equiv\ 2n-x\ (mod\ 2n)$
同理纵坐标要从0变成y,也只有两种情况：
$t \equiv\ y\ (mod\ 2m)$
$t \equiv\ 2m-y\ (mod\ 2m)$
同时考虑横纵坐标,一共四种情况,每次相当于解一个线性同余方程组。
解线性同余方程组可以参考这篇： http://www.cnblogs.com/vb4896/p/4009181.html
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <set>
#include <queue>
using namespace std; #define X first
#define Y second
#define Mod 1000000007
#define N 200110
#define M 200110 typedef long long ll;
typedef pair<int,int> pii; const ll INF=4e18; void ex_gcd(ll a,ll b,ll &x,ll &y,ll &d)
{
if (b==){x=,y=,d=a;}
else
{
ex_gcd(b,a%b,y,x,d);
y-=a/b*x;
}
} ll Solve(ll a1,ll a2,ll m1,ll m2)
{
ll x,y,d,lcm;
ex_gcd(m1,m2,x,y,d);
if ((a2-a1)%d!=) return INF; lcm=m1/d*m2;
x*=(a2-a1)/d;
x=x*m1+a1;
x=(x%lcm)+lcm;
if (x>=lcm) x-=lcm; return x;
} int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout); int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for (int i=;i<=k;i++)
{
ll ans=INF; int x,y;
scanf("%d%d",&x,&y);
ans=min(ans,Solve(x,y,*n,*m));
ans=min(ans,Solve(*n-x,y,*n,*m));
ans=min(ans,Solve(*n-x,*m-y,*n,*m));
ans=min(ans,Solve(x,*m-y,*n,*m));
if (ans==INF) ans=-;
printf("%I64d\n",ans);
} return ;
}
再来一发福利： hdu 5114 和这题的方法类似,可以顺手切了
http://acm.hdu.edu.cn/showproblem.php?pid=5114
题目大意：
n*m的盒子里给出2个球的坐标,2个球一开始速度都是(1,1),遵守反射定律,求相遇点的坐标。
思路：
1.首先相遇点的坐标要么是整数,要么是n+0.5的形式,所以可以实现把所有坐标乘以2,可以避免小数,最后除以2就好。
2.同样横纵坐标分开考虑。
不难求出横纵坐标第一次相同的时间分别为$\frac{2n-x_1-x_2}{2}$ $\frac{2m-y_1-y_2}{2}$
然后水平方向相遇的周期为n,竖直方向周期为m。所以
$t \equiv\ \frac{2n-x_1-x_2}{2}\ (mod\ n)$
$t \equiv\ \frac{2m-y_1-y_2}{2}\ (mod\ m)$
解出t,然后模拟一下就可以求出相遇点的坐标了。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std; #define N 1010
typedef long long ll; int T,n,m,x1,x2,y1,y2; void ex_gcd(ll a,ll b,ll &x,ll &y,ll &d)
{
if (b==) {x=,y=,d=a;}
else
{
ex_gcd(b,a%b,y,x,d);
y-=a/b*x;
}
} ll Solve()
{
if (x1==x2 && y1==y2) return ;
if (x1==x2) return (*m-y1-y2)/;
if (y1==y2) return (*n-x1-x2)/; ll t1=(*n-x1-x2)/,t2=(*m-y1-y2)/,x,y,d;
ex_gcd(n,m,x,y,d);
if ((t2-t1)%d!=) return -;
x*=(t2-t1)/d; ll lcm=n/d*m;
ll ans=(x*n+t1)%lcm;
if (ans<) ans+=lcm;
return ans;
} int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout); scanf("%d",&T);
for (int cas=;cas<=T;cas++)
{
printf("Case #%d:\n",cas);
scanf("%d%d",&n,&m); n<<=,m<<=;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1<<=,y1<<=,x2<<=,y2<<=;
ll t=Solve();
if (t==-) {printf("Collision will not happen.\n"); continue;} int tx=t%(*n),ty=t%(*m),x=x1,y=y1;
if (x+tx<=n) tx=x+tx;
else if (*n-x-tx>=) tx=*n-x-tx;
else tx-=n+n-x; if (y+ty<=m) ty=y+ty;
else if (*m-y-ty>=) ty=*m-y-ty;
else ty-=m+m-y; printf("%.1lf %.1lf\n",tx/2.0,ty/2.0);
} return ;
}