首页 > 代码库 > Collision(hdu5114)
Collision(hdu5114)
Collision
Time Limit: 15000/15000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)
Total Submission(s): 846 Accepted Submission(s): 200
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.
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 ≤ 105)
The next line contains four integers x1, y1, x2, y2. The initial position of the two balls is (x1, y1) and (x2, y2). (0 ≤ x1, x2 ≤ x; 0 ≤ y1, y2 ≤ y)
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 ≤ 105)
The next line contains four integers x1, y1, x2, y2. The initial position of the two balls is (x1, y1) and (x2, y2). (0 ≤ x1, x2 ≤ x; 0 ≤ y1, y2 ≤ 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 xc and yc, rounded to one decimal place, which indicate the position where the two balls will first collide.
In the second line, output “Collision will not happen.” (without quotes) if the collision will never happen. Otherwise, output two real numbers xc and yc, 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 101 0 1 10
Sample Output
Case #1:6.0 6.0
Case #2:Collision will not happen.
Case #3:6.0 5.0
Hint
In first example, two balls move from (1, 1) and (9, 9) both with velocity (1, 1), the ball starts from (9, 9) will rebound at point (10, 10) then move with velocity (−1, −1). The two balls will meet each other at (6, 6).
思路:扩展欧几里德;
首先可以知道,要相遇肯定在整数点,和半数点处,那么我们先将所有的都乘以2,为了防止小数。
当x1 = x2的时候,那么无论啥时候,x1=x2;那么这个时候,只要求y1=y2的时刻,
ty =(m-(y2+(m-y1)))/2+m-y1 = (2*n-(y1+y2))/2;那么根据ty 可以求得坐标;
同理y1=y2;
那么当x1!=x2&&y1!=y2的时候,
得到t1 = tx+k1*n;t2 =ty+k2*m;
那么t2 = t1;所以解两个同余方程即可,取最小的t;
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<stdlib.h> 5 #include<string.h> 6 #include<math.h> 7 #include<queue> 8 using namespace std; 9 typedef long long LL; 10 pair<LL,LL>exgcd(LL n,LL m); 11 LL solve(LL x, LL y,LL n,LL m); 12 LL gcd(LL n,LL m); 13 int main(void) 14 { 15 LL n,m,k; 16 int N; 17 int __ca = 0; 18 scanf("%d",&N); 19 while(N--) 20 { 21 scanf("%lld %lld",&n,&m); 22 LL x1,y1,x2,y2; 23 n*=2; 24 m*=2; 25 scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2); 26 x1*=2; 27 y1*=2,x2*=2; 28 y2*=2; 29 printf("Case #%d:\n",++__ca); 30 if(x1==x2&&y1==y2) 31 { 32 printf("%.1f %.1f\n",x1/2,y1/2); 33 } 34 else if(x1==x2) 35 { 36 LL ty = (2*m-(y1+y2))/2; 37 LL yy = min(y1,y2)+ty; 38 LL xx = min(x1,x2)+ ty; 39 if((xx/n)%2==0) 40 { 41 xx = xx%n; 42 } 43 else 44 { 45 xx = ((n-xx)%n+n)%n; 46 if(xx == 0)xx = n; 47 } 48 if((yy/m)%2==0) 49 { 50 yy = yy%m; 51 } 52 else 53 { 54 yy = ((m-yy)%m+m)%m; if(yy == 0)yy = m; 55 } 56 printf("%.1lf %.1lf\n",xx/2.0,yy/2.0); 57 } 58 else if(y1 == y2) 59 { 60 LL tx = (2*n-(x1+x2))/2; 61 LL yy = min(y1,y2)+tx; 62 LL xx = min(x1,x2)+tx; 63 if((yy/m)%2==0) 64 { 65 yy = yy%m; 66 } 67 else 68 { 69 yy = ((m-yy)%m+m)%m; 70 if(yy == 0)yy = m; 71 } 72 if((xx/n)%2==0) 73 { 74 xx = xx%n; 75 } 76 else 77 { 78 xx = ((n-xx)%n+n)%n; 79 if(xx == 0)xx = n; 80 } 81 printf("%.1lf %.1lf\n",xx/2.0,yy/2.0); 82 } 83 else 84 { 85 LL ty = (2*m-(y1+y2))/2; 86 LL tx = (2*n-(x1+x2))/2; 87 LL ask = solve(tx,ty,n,m); 88 if(ask==1e18) 89 printf("Collision will not happen.\n"); 90 else 91 { 92 LL yy = y1+ask; 93 if((yy/m)%2==0) 94 { 95 yy = yy%m; 96 //if(yy == 0)yy = m; 97 } 98 else 99 {100 yy = ((m-yy)%m+m)%m;101 if(yy == 0)yy = m;102 }103 LL xx = x1+ask;104 if((xx/n)%2==0)105 {106 xx = xx%n;107 }108 else109 {110 xx = ((n-xx)%n+n)%n;111 if(xx == 0)xx = n;112 }113 printf("%.1lf %.1lf\n",xx/2.0,yy/2.0);114 }115 }116 117 }118 return 0;119 }120 pair<LL,LL>exgcd(LL n,LL m)121 {122 if(m==0)123 return make_pair(1,0);124 else125 {126 pair<LL,LL>ak = exgcd(m,n%m);127 return make_pair(ak.second,ak.first-(n/m)*ak.second);128 }129 }130 LL solve(LL x, LL y,LL n,LL m)131 {132 LL cc = n;133 LL c = x-y;134 LL gc = gcd(n,m);135 if(c%gc)return 1e18;136 else137 {138 c/=gc;139 n/=gc;140 m/=gc;141 pair<LL,LL>ak = exgcd(n,m);142 LL x0 = (ak.first*c%m+m)%m;143 LL lcm = (LL)m*cc;144 x = x-cc*x0;145 x = x%lcm+lcm;146 x%=lcm;147 return x;148 }149 }150 LL gcd(LL n,LL m)151 {152 if(m==0)return n;153 else return gcd(m,n%m);154 }
Collision(hdu5114)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。