UVa 10180 - Rope Crisis in Ropeland!

タイトルリンク:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=41&page=show_problem&problem=1121
标题:2点の座標を与えて、1本の最も短い線(曲線あるいは直線)でつながって、座標系の中原の点のところに半径Rの円があって、連線はこの円を通り抜けることができません.
分析:

この問題は私が何度もWAしました.なぜならdoubleの座標をintにしたからです.o(′□╰)o

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 
 5 const double PI = acos( -1.0 );
 6 
 7 struct point
 8 {
 9     double x, y;
10 };
11 
12 point O;  //    
13 
14 double Get_Dist( point &a, point &b )    //       
15 {
16     return sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y )*(a.y - b.y) );
17 }
18 
19 double Get_Angle( double a, double b, double c )  //       
20 {
21     return acos( (b*b + c*c - a*a) / (2*b*c) );
22 }
23 
24 bool check( point &m, point &n, double x, double y )  //    ( x, y )     m, n   
25 {
26     double minx = m.x < n.x ? m.x : n.x;
27     double maxx = m.x > n.x ? m.x : n.x;
28     double miny = m.y < n.y ? m.y : n.y;
29     double maxy = m.y > n.y ? m.y : n.y;
30     return ( x > minx && x <= maxx && y >= miny && y <= maxy );
31 }
32 
33 bool Judge( point &m, point &n, double &R )           //         
34 {
35     if ( m.x == n.x )                                 //   y     
36     {
37         if ( abs(m.x) >= R ) return true;
38         else
39         {
40             if ( m.y * n.y > 0 ) return true;
41             else return false;
42         }
43     }
44     else if ( m.y == n.y )                             //   x     
45     {
46         if ( abs(m.y) >= R ) return true;
47         else
48         {
49             if ( m.x * n.x > 0 ) return true;
50             else return false;
51         }
52     }
53 
54     double A = n.y - m.y;                              //       ，        ，  A, B, C
55     double B = m.x - n.x;
56     double C = (n.x - m.x) * m.y - (n.y - m.y) * m.x;
57     double dis = abs(C)/ sqrt( A*A + B*B );            //        
58     if ( dis >= R ) return true;
59     else
60     {
61         double kkk = (-A) / B;
62         double bbb = (-C) / B;
63         double xx = ( -bbb ) / ( kkk + 1.0 / kkk );
64         double yy = ( (-1.0) / kkk ) * xx;
65         if ( check( m, n, xx, yy ) ) return false;     //       
66         else return true;                              //        
67     }
68 }
69 
70 int main()
71 {
72     int T;
73     double R;
74     point A, B;
75     O.x = 0;
76     O.y = 0;
77     scanf( "%d", &T );
78     while ( T-- )
79     {
80         scanf( "%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &R );
81 
82         if ( Judge(A, B, R) )                             //        
83             printf( "%.3f
", Get_Dist(A, B) );
84         else                                              //       
85         {
86             double L1 = Get_Dist(A, O);
87             double L2 = Get_Dist(B, O);
88             double LL1 = sqrt( L1*L1 - R*R );
89             double LL2 = sqrt( L2*L2 - R*R );
90             double angle = Get_Angle( Get_Dist(A, B), L1, L2 ) - acos( R/L1 ) - acos( R/L2 );
91             double ans = LL1 + LL2 + R * angle;
92             printf( "%.3f
", ans );
93         }
94     }
95     return 0;
96 }