首页 > 代码库 > hdu 5572 An Easy Physics Problem 圆+直线
hdu 5572 An Easy Physics Problem 圆+直线
An Easy Physics Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1430 Accepted Submission(s): 270
Problem Description
On an infinite smooth table, there‘s a big round fixed cylinder and a little ball whose volume can be ignored.
Currently the ball stands still at point A, then we‘ll give it an initial speed and a direction. If the ball hits the cylinder, it will bounce back with no energy losses.
We‘re just curious about whether the ball will pass point B after some time.
Currently the ball stands still at point A, then we‘ll give it an initial speed and a direction. If the ball hits the cylinder, it will bounce back with no energy losses.
We‘re just curious about whether the ball will pass point B after some time.
Input
First line contains an integer T, which indicates the number of test cases.
Every test case contains three lines.
The first line contains three integers Ox, Oy and r, indicating the center of cylinder is (Ox,Oy) and its radius is r.
The second line contains four integers Ax, Ay, Vx and Vy, indicating the coordinate of A is (Ax,Ay) and the initial direction vector is (Vx,Vy).
The last line contains two integers Bx and By, indicating the coordinate of point B is (Bx,By).
⋅ 1 ≤ T ≤ 100.
⋅ |Ox|,|Oy|≤ 1000.
⋅ 1 ≤ r ≤ 100.
⋅ |Ax|,|Ay|,|Bx|,|By|≤ 1000.
⋅ |Vx|,|Vy|≤ 1000.
⋅ Vx≠0 or Vy≠0.
⋅ both A and B are outside of the cylinder and they are not at same position.
Every test case contains three lines.
The first line contains three integers Ox, Oy and r, indicating the center of cylinder is (Ox,Oy) and its radius is r.
The second line contains four integers Ax, Ay, Vx and Vy, indicating the coordinate of A is (Ax,Ay) and the initial direction vector is (Vx,Vy).
The last line contains two integers Bx and By, indicating the coordinate of point B is (Bx,By).
⋅ 1 ≤ T ≤ 100.
⋅ |Ox|,|Oy|≤ 1000.
⋅ 1 ≤ r ≤ 100.
⋅ |Ax|,|Ay|,|Bx|,|By|≤ 1000.
⋅ |Vx|,|Vy|≤ 1000.
⋅ Vx≠0 or Vy≠0.
⋅ both A and B are outside of the cylinder and they are not at same position.
Output
For every test case, you should output "Case #x: y", where x indicates the case number and counts from 1. y is "Yes" if the ball will pass point B after some time, otherwise y is "No".
Sample Input
20 0 12 2 0 1-1 -10 0 1-1 2 1 -11 2
Sample Output
Case #1: NoCase #2: Yes
Source
2015ACM/ICPC亚洲区上海站-重现赛(感谢华东理工)
题意:有一个质点位于点(x,y),初速度为(vx,vy),有一个柱子位于(ox,oy)半径为r,假设质点碰到柱子后发生弹性碰撞,问是否质点能经过(bx,by)
#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <iostream>#include <cmath>#include <map>#include <bitset>#include <stack>#include <queue>#include <vector>#include <bitset>#include <set>#define MM(a,b) memset(a,b,sizeof(a));#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;typedef unsigned long long ull;#define CT continue#define SC scanfconst double eps=1e-8;int dcmp(double x){ if(fabs(x)<eps) return 0; else return x>0?1:-1;}struct Point { double x,y; void read() { SC("%lf%lf",&x,&y); }};struct circle{ Point o; int r; void read() { SC("%lf%lf%d",&o.x,&o.y,&r); }};Point operator-(Point a,Point b){ return (Point){a.x-b.x,a.y-b.y};}Point operator+(Point a,Point b){ return (Point){a.x+b.x,a.y+b.y};}Point operator*(double p,Point a){ return (Point){a.x*p,a.y*p};}double dot(Point a,Point b){ return a.x*b.x+a.y*b.y;}double dis(Point a){ return sqrt(dot(a,a));}double cross(Point a,Point b){ return a.x*b.y-b.x*a.y;}Point GetLineProjection(Point P,Point A,Point B){ Point v=B-A; Point ans=A+(dot(v,P-A)/dot(v,v))*v; return ans;}Point jiaoa,jiaob,tou;double d;void getjiaopoint(Point pa,Point pav,circle C){ Point A=pa,B=pa+pav; if(dis(C.o-B)>dis(C.o-A)){ A=pa+pav; B=pa; } tou=GetLineProjection(C.o,A,B); d=dis(tou-C.o); if(dcmp(d-C.r)<0) { double l=sqrt((double)C.r*C.r-d*d); jiaoa=tou+l/dis(B-A)*(B-A); jiaob=tou-l/dis(B-A)*(B-A); }}int main(){ int cas;SC("%d",&cas); circle C; int kk=0; Point pa,pb,pav; while(cas--) { C.read(); pa.read();pav.read();pb.read(); getjiaopoint(pa,pav,C); if(dcmp(d-C.r)>=0) { if(dcmp(cross(pb-pa,pav))==0&&dcmp(dot(pb-pa,pav))>0) printf("Case #%d: Yes\n",++kk); else printf("Case #%d: No\n",++kk); CT; } Point chap; if(dcmp(dis(jiaoa-pa)-dis(jiaob-pa))<0) chap=jiaoa; else chap=jiaob; int flag=0; if(dcmp(cross(pa-pb,chap-pb))==0&&dcmp(dot(pa-pb,chap-pb))<=0) flag=1; Point I=GetLineProjection(pa,C.o,chap); Point pa2=pa+2*(I-pa),pa2v=chap-pa2; if(dcmp(cross(pb-chap,pa2v))==0&&dcmp(dot(pb-chap,pa2v))<=0) flag=1; if(flag) printf("Case #%d: Yes\n",++kk); else printf("Case #%d: No\n",++kk); } return 0;}
分析:
1.直接根据向量求出角度再比大小容易错(精度),可做a点关于直线的对称点a2,再判断b点是否在chap与a2该条射线上
pa
hdu 5572 An Easy Physics Problem 圆+直线
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。