hdu 5114 Collision

Collision

Time Limit: 15000/15000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 1645 Accepted Submission(s): 442

Problem Description

Matt is playing a naive computer game with his deeply loved pure girl.

The playground is a rectangle with walls around. Two balls are put in different positions inside the rectangle. The balls are so tiny that their volume can be ignored. Initially, two balls will move with velocity (1, 1). When a ball collides with any side of the rectangle, it will rebound without loss of energy. The rebound follows the law of refiection (i.e. the angle at which the ball is incident on the wall equals the angle at which it is reflected).

After they choose the initial position, Matt wants you to tell him where will the two balls collide for the first time.

Input

The first line contains only one integer T which indicates the number of test cases.

For each test case, the first line contains two integers x and y. The four vertices of the rectangle are (0, 0), (x, 0), (0, y) and (x, y). (1 ≤ x, y ≤ 10⁵)

�The next line contains four integers x₁, y₁, x₂, y₂. The initial position of the two balls is (x₁, y₁) and (x₂, y₂). (0 ≤ x₁, x₂ ≤ x; 0 ≤ y₁, y₂ ≤ y)

Output

For each test case, output “Case #x:” in the first line, where x is the case number (starting from 1).

In the second line, output “Collision will not happen.” (without quotes) if the collision will never happen. Otherwise, output two real numbers x_c and y_c, rounded to one decimal place, which indicate the position where the two balls will first collide.

Sample Input

3

10 10

1 1 9 9

10 10

0 5 5 10

10 10

1 0 1 10

Sample Output

Case #1:

6.0 6.0

Case #2:

Collision will not happen.

Case #3:

6.0 5.0

题目大意：两个球在一个矩形里面做完全弹性碰撞的运动，位置给出，速度恒为(1,1)。 

问它们会不会碰撞到一起，会的话第一次碰撞在哪个点？

思路：对速度进行正交分解。为了避免小数，所有数据*2。

分情况讨论：

1、如果两个点重合，直接输出那个点。

2、如果横坐标相同讨论纵坐标的情况。

3、如果纵坐标相同讨论横坐标的情况

4、都不相同。那么可列出两个同余方程组来

假如tx代表在x轴上运动了tx时间两点横坐标相同。

那么有(假设x1>x2)  n-（x1+tx-n）=x2+tx 。 即 tx=n-(x1+x2)/2 ；（这也是为什么数据都乘2的原因）

同理我们可以列得y轴上的方程。

扩展欧几里得算法求解同余方程。

（ps:写这题目一定要仔细！！！因为把m写成了n，弄得wa了好多遍，查了一个多小时的bug）

繁琐的AC代码：

#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y){
   if(b==0){
       x=1;
       y=0;
       return a;
   }
   ll gcd=exgcd(b,a%b,x,y);
   ll t=x;
   x=y;
   y=t-(a/b)*y;
   return gcd;
}
int main(){
   int T;
   cin>>T;
   for(int times=1;times<=T;times++){
       ll n,m;
       cin>>n>>m;
       ll x1,x2,y1,y2;
       cin>>x1>>y1>>x2>>y2;
       n=2*n; m=2*m; x1=2*x1; y1=2*y1; x2=2*x2; y2=2*y2;
       ll ansx,ansy;
       printf("Case #%d:
",times);
       if(x1==x2&&y1==y2){
           ansx=x1;
           ansy=y1;
           printf("%.1f %.1f
",ansx/2,ansy/2);
       }else if(x1==x2){
           ll tb=m-(y1+y2)/2;
           x1=(x1+tb)%(2*n);
           y1=(y1+tb)%(2*m);
           if(x1>n){
               ansx=n-(x1-n);
           }else{
               ansx=x1;
           }
           if(y1>m){
               ansy=m-(y1-m);
           }else{
               ansy=y1;
           }
           printf("%.1f %.1f
",ansx/2.0,ansy/2.0);
       }else if(y1==y2){
           ll ta=n-(x1+x2)/2;
           x1=(x1+ta)%(2*n);
           y1=(y1+ta)%(2*m);
           if(x1>n){
               ansx=n-(x1-n);
           }else{
               ansx=x1;
           }
           if(y1>m){
               ansy=m-(y1-m);
           }else{
               ansy=y1;
           }
           printf("%.1f %.1f
",ansx/2.0,ansy/2.0);
       }else{
           ll ta=n-(x1+x2)/2;
           ll tb=m-(y1+y2)/2;
           ll x,y,gcd,c;
           c=tb-ta;
           gcd=exgcd(n,m,x,y);
           if(c%gcd!=0){
               printf("Collision will not happen.
");
           }else{
               ll r=m/gcd;
               x=((x*c/gcd)%r+r)%r;
               ll t=ta+x*n;
               ll tmpx,tmpy;
               tmpx=(x1+t)%(2*n);
               tmpy=(y1+t)%(2*m);
               if(tmpx>n){
                   tmpx=n-(tmpx-n);
               }
               if(tmpy>m){
                   tmpy=m-(tmpy-m);   //就是这里！！！第二个m写成了n！！！
               }
               ansx=tmpx;
               ansy=tmpy;
               printf("%.1f %.1f
",ansx/2.0,ansy/2.0);
           }
       }
   }
   return 0;
}

简单的代码来源：https://www.cnblogs.com/TenderRun/p/5943453.html

/*
愣是照着这个代码查了半天都没查出之前代码为什么wa，后面还是不经意间发现的！！！
如果一开始就按这个代码写，讨论情况的时候会简单很多。orz
*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
LL ta,tb,x,y,tim;
int T,cas,n,m,x1,y1,x2,y2;
LL Exgcd(LL a,LL b,LL&x,LL&y){
   if(b==0){x=1,y=0;return a;}
   LL ret=Exgcd(b,a%b,y,x);
   y-=a/b*x;return ret;
}
int main(){
   scanf("%d",&T);
   while(T--){
       scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);
       n*=2;m*=2;x1*=2;y1*=2;x2*=2;y2*=2;
       ta=n-(x1+x2)/2;tb=m-(y1+y2)/2;
       printf("Case #%d:
",++cas);tim=-1;
       if(x1==x2&&y1==y2)tim=0;
       if(x1!=x2&&y1==y2)tim=ta;
       if(x1==x2&&y1!=y2)tim=tb;
       if(x1!=x2&&y1!=y2){
           LL d=Exgcd(n,m,x,y);
           if((tb-ta)%d==0){
               x=(tb-ta)/d*x;
               x=(x%(m/d)+m/d)%(m/d);
               tim=ta+n*x;
           }
       }
       if(tim==-1)
           puts("Collision will not happen.");
       else{
           x1=(x1+tim)%(2*n);y1=(y1+tim)%(2*m);
           if(x1>n)x1=2*n-x1;if(y1>m)y1=2*m-y1;
           printf("%.1f %.1f
",x1/2.0,y1/2.0);
       }    
   }
   return 0;
}