[计算几何]HDU_3834 2011多校第一场-HNU
这题一开始以为很难,然后直接pass了,后来看到有人写解题报告才70+行的代码,于是决定写这题--||||.写到一半无奈那位朋友的方法不懂,好吧那自己慢慢搞吧[那位朋友貌似用复数搞的,无限ym啊]然后搞了好久一直处于样例不过的状态,而且网上解题报告很少.一直查思路,查代码.一直觉得自己思路是对的[自己当然觉得自己是对的了--||],后来幸运搞到几组数据,然后各种改啊,就过了,下面是思路:
首先可以把打圆平移到和原点重合,然后大圆半径减去小圆半径.再处理其他的.然后小圆变成一个点
1.算出小圆和和大圆第一碰撞所需时间,如果所给时间比这个时间短,直接算,否则进入2
2.算出第一次碰撞的交点,和相应的夹角,假设圆心为0,小圆起始点为A,碰撞点为B,第二次碰撞的交点为C,算出角ABO的大小,然后可以算出BC的长度和所需要的时间,这样就可以了
3.得到上面的信息之后,可以算出经过整数次弦长之后,还剩下多少时间,以及所处的位置和当前的速度方向,然后剩下的就简单了.最后再把大圆的圆心反原回去即可
要注意的是旋转的时候一定要考虑到底是顺时针还是逆时针,我就是因为这个WA了n次!!!
附上代码:
1. /
2. 1.把圆心移到原点
3. 2.大圆的半径减掉小圆的半径
4.
5. !!!用到斜率就要注意 斜率为0的情况!!!
6.
7. 1.角度问题,首先 对acos来说 i和2pi-i是一样的
8. 还有atan2(y,x)得到y/x的正切值,返回值为[-pi,pi]
9. 这里还有一个角度问题就是转的时候可能是顺时针转
10. 也就是角度旋转的时候不是用加了而是用减!!!!!!!
11. 代码中的flag就是用来判断顺时针还是逆时针的
12. 还有一个就是向量旋转的表达式
13. /
14. #include
15. #include
16. #include
17. #include
18.
19. const double eps = 1e-6
20. const double pi = acos(-1.0);
21.
22. typedef struct
23. {
24. double x,y;
25. }TPoint;
26.
27. typedef struct
28. {
29. double x,y,r;
30. }TCircle;
31.
32. TCircle ball,sball;
33. TPoint vec,convert;
34. double T;
35. int flag;
36.
37. inline double squ(double x)
38. {
39. return xx;
40. }
41.
42. double dot(TPoint a,TPoint b,TPoint c)
43. {
44. return (b.x-a.x)(c.x-a.x)+(b.y-a.y)(c.y-a.y);
45. }
46.
47. int cross(TPoint a,TPoint b,TPoint c)
48. {
49. double ret = (b.x-a.x)(c.y-a.y)-(b.y-a.y)(c.x-a.x);
50. if(ret>eps)
51. return 1
52. return -1
53. }
54. void work()
55. {
56. convert.x = ball.x;
57. convert.y = ball.y;
58.
59. sball.x -= convert.x;
60. sball.y -= convert.y;
61. ball.x =0
62. ball.y = 0
63. ball.r -= sball.r;
64.
65. TPoint me = {sball.x,sball.y};
66.
67. if(fabs(vec.x) < eps & fabs(vec.y) < eps)
68. {/vec is zero/
69. me.x += convert.x;
70. me.y += convert.y;
71. printf(“%.1f %.1f\n”,me.x,me.y);
72. return
73. }
74. if(fabs(ball.r)
75. {/sball.r == ball.r/
76. me.x += convert.x;
77. me.y += convert.y;
78. printf(“%.1f %.1f\n”,me.x,me.y);
79. return
80. }
81.
82. if(squ(me.x+Tvec.x)+squ(me.y+Tvec.y)+eps
83. {
84. me.x = me.x+Tvec.x;
85. me.y = me.y+Tvec.y;
86. me.x += convert.x;
87. me.y += convert.y;
88. printf(“%.1f %.1f\n”,me.x,me.y);
89. return ;
90. }
91.
92.
93. double k=vec.y/vec.x;
94. double b=me.y-kme.x;
95. double x1;
96.
97. //printf(“k:%f b:%f %f\n”,k,b,ball.r);
98. if(vec.x<0)
99. {
100. x1=(-kb-sqrt(squ(kball.r)+squ(ball.r)-squ(b)))/(squ(k)+1);
101. }
102. else
103. {
104. x1=(-kb+sqrt(squ(kball.r)+squ(ball.r)-squ(b)))/(squ(k)+1.0);
105. }
106. /fjjjjj/
107. double y1=kx1+b;
108. /
109. x1 & y1
110. /
111. // printf(“(x1,y1)%f %f\n”,x1,y1);
112.
113.
114. TPoint tmp1 = {x1,y1};
115. TPoint tmp2 = {0,0};
116. double u = dot(tmp1,tmp2,me);
117. flag = cross(tmp1,tmp2,me);
118.
119. /
120. flag
121. /
122. //printf(“flag:%d\n”,flag);
123.
124. u = u/(sqrt(squ(x1-me.x)+squ(y1-me.y))ball.r);
125.
126. double l=(u)ball.r;
127. l *= 2
128. u = acos(u);
129.
130. /
131. l
132. /
133. //printf(“l:%f\n”,l);
134.
135.
136. double t1 = l/sqrt(squ(vec.x)+squ(vec.y));
137.
138. __int64 time = (T-(x1-me.x)/vec.x)/t1;
139.
140. /
141. time
142. /
143. //printf(“time:%I64d\n”,time);
144.
145. T = T-(x1-me.x)/vec.x-time*t1;
146.
147. /
148. lefttime
149. */
150. // printf(“lefttime:%f\n”,T);
151.
152.
153. /上面以对 很可能是角度算错了 下面的要仔细验证下!!!/
154. double u2=atan2(y1,x1);
155. double u3 = (time+1)(pi-2u)flag;
156. u2 += time(pi-2u)flag;
157. double x2 = ball.rcos(u2);
158. double y2 = ball.rsin(u2);
159.
160. //printf(“%f %f(x2,y2)\n”,x2,y2);
161. TPoint vec2;
162.
163. vec2.x = vec.xcos(u3)-vec.ysin(u3);
164. vec2.y = vec.xsin(u3)+vec.ycos(u3);
165.
166. me.x = x2+vec2.xT+convert.x;
167. me.y = y2+vec2.y*T+convert.y;
168. printf(“%.1f %.1f\n”,me.x,me.y);
169. return
170. }
171. int main(void)
172. {
173. #ifndef ONLINE_JUDGE
174. freopen(“G.in”,“r”,stdin);
175. freopen(“G.out”,“w”,stdout);
176. #endif
177. int t;
178. scanf(“%d”,t);
179. while(t–)
180. {
181. scanf(“%lf%lf%lf”,ball.x,&ball.y,&ball.r);
182. scanf(“%lf%lf%lf”,sball.x,&sball.y,&sball.r);
183. scanf(“%lf%lf%lf”,vec.x,&vec.y,&T);
184. work();
185. }
186. return 0
187. }
