首页 > 代码库 > 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.
 

 

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 OxOy and r, indicating the center of cylinder is (Ox,Oy) and its radius is r.

The second line contains four integers AxAyVx 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.

 Vx0 or Vy0.

 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 1y 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 圆+直线