Advertisement
Guest User

Untitled

a guest
Apr 7th, 2016
275
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define readFile freopen("in.txt","r",stdin)
  4. #define writeFile freopen("out.txt","w",stdout)
  5. #define fastio ios_base::sync_with_stdio(false)
  6.  
  7. using namespace std;
  8.  
  9. const int N = 100010;
  10. const long long M = 1e9 + 7;
  11.  
  12. #define eps 1e-9
  13. #define PI acos(-1.0)
  14.  
  15. double sqr(double x){
  16.     return x*x;
  17. }
  18.  
  19. struct point{
  20.     double x,y;
  21.     point():x(0),y(0){}
  22.     point(double x, double y):x(x),y(y){}
  23.    
  24.     double dist(const point &p){
  25.         return hypot(this->x-p.x,this->y-p.y);
  26.     }
  27. };
  28.  
  29. struct circle{
  30.     point p;
  31.     double r;
  32.     circle():p(),r(0){}
  33.     circle(point p, double r):p(p.x,p.y),r(r){}
  34. };
  35.  
  36. struct line{
  37.     // ax + by + c = 0;
  38.     double a,b,c;
  39.     line(){}
  40.     line(double a, double b, double c):a(a),b(b),c(c){}
  41.     line(point p1, point p2){
  42.         if(abs(p1.x-p2.x) < eps){ // vertical
  43.             a = 1.0;
  44.             b = 0.0;
  45.             c = -p1.x;
  46.         }
  47.         else{
  48.             a = -(p1.y-p2.y)/(p1.x-p2.x);
  49.             b = 1.0;
  50.             c = -(a*p1.x)-p1.y;
  51.         }
  52.     }
  53. };
  54.  
  55. struct triangle{
  56.     double a,b,c;
  57.     triangle(){}
  58.     triangle(point p1, point p2, point p3){
  59.         a = p1.dist(p2);
  60.         b = p2.dist(p3);
  61.         c = p1.dist(p3);
  62.     }
  63.    
  64.     double area(){
  65.         double sp = (a+b+c)/2.0;
  66.         double res = sp*(sp-a)*(sp-b)*(sp-c);
  67.         return sqrt(res);
  68.     }
  69.    
  70.     double findTheta(){
  71.         double aa = a, bb = b, cc = c;
  72.         if(bb > aa) swap(aa,bb);
  73.         if(cc > aa) swap(aa,cc);
  74.         double costheta = (sqr(bb)+sqr(cc)-sqr(aa))/(2.0*bb*cc);
  75.         return acos(costheta);
  76.     }
  77. };
  78.  
  79. int lineCircleIntersection(circle cr, line l, point &p1, point &p2){
  80.     if(abs(l.b)<eps){ // Vertical line, the equation is already solved for x .
  81.         double a = 1.0;
  82.         double b = -2.0 * cr.p.y;
  83.         double c =  sqr(l.c/l.a-cr.p.x) + sqr(cr.p.y) - sqr(cr.r);
  84.         double d = sqr(b) - 4.0 * a * c;
  85.         if(d+eps < 0) return 0; // No intersection .
  86.         if(abs(d) < eps){
  87.             p1.x = l.c/l.a;
  88.             p1.y = -b/(2.0*a);
  89.             return 1; // Tangent line .
  90.         }
  91.         double dd = sqrt(d);
  92.         p1.x = p2.x = l.c/l.a;
  93.         p1.y = (-b+dd)/(2.0*a);
  94.         p2.y = (-b-dd)/(2.0*a);
  95.         return 2; // Intersect in two points .
  96.     }
  97.     else{
  98.         double a = 1.0 + l.a;
  99.         double b = 2.0 * (l.a*l.c - cr.p.x + cr.p.y*l.a);
  100.         double c = sqr(cr.p.x) + sqr(cr.p.y) + sqr(l.c) - sqr(cr.r) - (2.0*cr.p.y*l.c);
  101.         double d = sqr(b) - 4.0 * a * c;
  102.         if(d+eps < 0) return 0; // No intersection .
  103.         if(abs(d) < eps){
  104.             p1.x = -b/(2.0*a);
  105.             p1.y = -p1.x - l.c;
  106.             return 1; // Tangent line .
  107.         }
  108.         double dd = sqrt(d);
  109.         p1.x = (-b+dd)/(2.0*a);
  110.         p1.y = -(p1.x*l.a) - l.c;
  111.         p2.x = (-b-dd)/(2.0*a);
  112.         p2.y = -(p2.x*l.a) - l.c;
  113.         return 2; // Intersect in two points .
  114.     }
  115. }
  116.  
  117. int main() {
  118. #ifndef ONLINE_JUDGE
  119.     readFile;
  120. #endif
  121.     fastio;
  122.     int t,tt = 1; cin >> t;
  123.     while(t--){
  124.         double x,y,z; cin >> x >> y >> z;
  125.         circle c(point(x,y),z);
  126.         double x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
  127.         point p1(x1,y1),p3(x2,y2);
  128.         point p2(p1.x,p3.y);
  129.         line l1(p2,p3), l2(p1,p2);
  130.        
  131.         point pt1,pt2,cl1,cl2;
  132.         int res = lineCircleIntersection(c,l1,pt1,pt2);
  133.         if(res==2){
  134.             if(pt1.x > pt2.x) cl1 = pt1;
  135.             else if(pt2.x > pt1.x) cl1 = pt2;
  136.             else if(pt1.y < pt2.y) cl1 = pt1;
  137.             else cl1 = pt2;
  138.         }
  139.         else cl1 = pt1;
  140.        
  141.         res = lineCircleIntersection(c,l2,pt1,pt2);
  142.         if(res==2){
  143.             if(pt1.y < pt2.y) cl2 = pt1;
  144.             else if(pt2.y < pt1.y) cl2 = pt2;
  145.             else if(pt1.x > pt2.x) cl2 = pt1;
  146.             else cl2 = pt2;
  147.         }
  148.         else cl2 = pt1;
  149.        
  150.         triangle t1(cl1,cl2,c.p);
  151.         double cseg = ((t1.findTheta()*sqr(c.r))/2.0)-t1.area();
  152.        
  153.         triangle t2(cl1,p2,cl2);
  154.         double ans = cseg + t2.area();
  155.        
  156.         cout << "Case " << tt++ << ": ";
  157.         cout << fixed << setprecision(8) << ans << "\n";
  158.     }
  159.     return 0;
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement