2013 ACM区域赛长沙 C Collision HDU 4793

题意：在平面上0,0点，有一个半径为R的圆形区域，并且在0,0点固定着一个半径为RM（<R）的圆形障碍物，现在圆形区域外x,y，有一个半径为r的，并且速度为vx,vy的硬币，如果硬币碰到了障碍物，将会保持原有的速度向反射的方向继续前进，现在给出R,RM,r,x,y,vx,vy，问硬币的任意部分在圆形区域中滑行多少时间？

思路：首先把R,RM加上r，就可以把硬币看做一个点来讨论了，然后算一下射线与这两个圆交点的个数，记作C1，C2，CM1，CM2,若与两个圆的交点数都是2，答案就是dis(c1,c2)-dis(cm1,cm2)之后再除以合成后的速度，若与大圆的交点数为2，小圆的交点数是0或者1，答案就是 dis（c1,c2）/速度，否则肯定是0了.

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<algorithm>
  6 #include<map>
  7 #include<queue>
  8 #include<set>
  9 #include<stack>
 10 #include<cmath>
 11 #include<vector>
 12 #define inf 0x3f3f3f3f
 13 #define Inf 0x3FFFFFFFFFFFFFFFLL
 14 #define eps 1e-9
 15 #define pi acos(-1.0)
 16 using namespace std;
 17 typedef long long ll;
 18 
 19 int dcmp(double x) {
 20     return (x>eps)-(x<-eps);
 21 }
 22 
 23 typedef struct Point {
 24     double x, y;
 25     Point(double x = 0, double y = 0) : x(x), y(y) {}
 26     Point operator+(const Point& p) const {
 27         return Point(x+p.x, y+p.y );
 28     }
 29     Point operator-(const Point& p) const {
 30         return Point(x-p.x, y-p.y );
 31     }
 32     Point operator*(const double d) const {
 33         return Point(x*d, y*d );
 34     }
 35     Point operator/(const double d) const {
 36         return Point(x/d, y/d );
 37     }
 38     void read() {
 39         scanf("%lf%lf", &x, &y);
 40     }
 41 } Vector;
 42 
 43 inline double Dis(const Point& a, const Point& b) {
 44     return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
 45 }
 46 
 47 struct Line {
 48     Point P;
 49     Vector v;
 50     double ang;
 51     Line() {}
 52     Line(const Point& P, const Vector& v):P(P),v(v) {
 53         ang = atan2(v.y,v.x);
 54     }
 55     bool operator<(const Line& L) const {
 56         return ang<L.ang;
 57     }
 58     Point point(double t) {
 59         return P+v*t;
 60     }
 61 };
 62 
 63 struct Circle {
 64     Point c;
 65     double r;
 66     Circle() {}
 67 };
 68 
 69 int GetLineCircleIntersection(Line L, Circle C, double &t1, double &t2, vector<Point> &sol) {
 70     double a = L.v.x, b = L.P.x-C.c.x, c = L.v.y, d = L.P.y - C.c.y;
 71     double e = a*a+c*c, f = 2*(a*b+c*d), g = b*b+d*d-C.r*C.r;
 72     double delta = f*f-4*e*g;
 73     if(dcmp(delta)<0) return 0;
 74     if(dcmp(delta)==0) {
 75         t1 = t2 = -f/(2*e);
 76         sol.push_back(L.point(t1));
 77         return 1;
 78     }
 79     t1 = (-f-sqrt(delta))/(2*e);
 80     sol.push_back(L.point(t1));
 81     t2 = (-f+sqrt(delta))/(2*e);
 82     sol.push_back(L.point(t2));
 83     if(dcmp(t1)<0 || dcmp(t2)<0) return 0;
 84     return 2;
 85 }
 86 
 87 double R,RM,r,x,y,vx,vy;
 88 int n,m,k;
 89 
 90 int main() {
 91 //    freopen("in.txt","r",stdin);
 92     while(~scanf("%lf%lf%lf%lf%lf%lf%lf",&RM,&R,&r,&x,&y,&vx,&vy)) {
 93         Line l1(Point(x,y),Point(vx,vy));
 94         Circle c1,c2;
 95         c1.r=RM+r;
 96         c1.c.x=c1.c.y=0.0;
 97         c2.c.x=c2.c.y=0.0;
 98         c2.r=R+r;
 99         double db1=0.0,db2=0.0;
100         vector<Point> crs1;
101         vector<Point> crs2;
102         int num2=GetLineCircleIntersection(l1,c1,db1,db2,crs2);
103         int num1=GetLineCircleIntersection(l1,c2,db1,db2,crs1);
104 //        printf("num1:%d num2:%d
",num1,num2);
105         double len=0.0,ans=0.0;
106         double vv=sqrt(vx*vx+vy*vy);
107         if (num1==2 && num2==2) {
108             len=Dis(crs1[0],crs1[1])-Dis(crs2[0],crs2[1]);
109             printf("%.4lf
",len/vv);
110         } else if (num1==2) {
111             len=Dis(crs1[0],crs1[1]);
112             printf("%.4lf
",len/vv);
113         } else {
114             printf("0.0000
");
115         }
116     }
117     return 0;
118 }

View Code