Advertisement
Guest User

Untitled

a guest
May 7th, 2015
225
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.38 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <stdio.h>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8.  
  9. #ifndef max
  10.   #define max(a,b) (((a) > (b)) ? (a) : (b))
  11. #endif
  12. #ifndef min
  13.   #define min(a,b) (((a) < (b)) ? (a) : (b))
  14. #endif
  15.  
  16. /*
  17.  * Find the intersection point(s) of two circles,
  18.  * when their centers and radiuses are given (2D).
  19.  */
  20.  
  21. class Point2d{
  22. public:
  23.     Point2d() {}
  24.     Point2d(double x, double y)
  25.         : X(x), Y(y) {}
  26.  
  27.     double x() const { return X; }
  28.     double y() const { return Y; }
  29.  
  30.     /**
  31.      * Returns the norm of this vector.
  32.      * @return the norm
  33.     */
  34.     double norm() const {
  35.         return sqrt( X * X + Y * Y );
  36.     }
  37.  
  38.     void setCoords(double x, double y) {
  39.         X = x; Y = y;
  40.     }
  41.  
  42.     // Print point
  43.     friend std::ostream& operator << ( std::ostream& s, const Point2d& p )  {
  44.       s << p.x() << " " << p.y();
  45.       return s;
  46.     }
  47. private:
  48.     double X;
  49.     double Y;
  50. };
  51.  
  52. class Circle{
  53. public:
  54.     /**
  55.      * @param R - radius
  56.      * @param C - center
  57.      */
  58.     Circle(double R, Point2d& C)
  59.         : r(R), c(C) {}
  60.  
  61.     /**
  62.      * @param R - radius
  63.      * @param X - center's x coordinate
  64.      * @param Y - center's y coordinate
  65.      */
  66.     Circle(double R, double X, double Y)
  67.         : r(R), c(X, Y) {}
  68.  
  69.     Point2d getC() const { return c; }
  70.     double getR() const { return r; }
  71.  
  72.     size_t intersect(const Circle& C2, Point2d& i1, Point2d& i2) {
  73.         // distance between the centers
  74.         double d = Point2d(c.x() - C2.c.x(),
  75.                 c.y() - C2.c.y()).norm();
  76.  
  77.         // find number of solutions
  78.         if(d > r + C2.r) // circles are too far apart, no solution(s)
  79.         {
  80.             std::cout << "Circles are too far apart\n";
  81.             return 0;
  82.         }
  83.         else if(d == 0 && r == C2.r) // circles coincide
  84.         {
  85.             std::cout << "Circles coincide\n";
  86.             return 0;
  87.         }
  88.         // one circle contains the other
  89.         else if(d + min(r, C2.r) < max(r, C2.r))
  90.         {
  91.             std::cout << "One circle contains the other\n";
  92.             return 0;
  93.         }
  94.         else
  95.         {
  96.             double a = (r*r - C2.r*C2.r + d*d)/ (2.0*d);
  97.             double h = sqrt(r*r - a*a);
  98.  
  99.             // find p2
  100.             Point2d p2( c.x() + (a * (C2.c.x() - c.x())) / d,
  101.                     c.y() + (a * (C2.c.y() - c.y())) / d);
  102.  
  103.             // find intersection points p3
  104.             i1.setCoords( p2.x() + (h * (C2.c.y() - c.y())/ d),
  105.                     p2.y() - (h * (C2.c.x() - c.x())/ d)
  106.             );
  107.             i2.setCoords( p2.x() - (h * (C2.c.y() - c.y())/ d),
  108.                     p2.y() + (h * (C2.c.x() - c.x())/ d)
  109.             );
  110.  
  111.             if(d == r + C2.r)
  112.                 return 1;
  113.             return 2;
  114.         }
  115.     }
  116.  
  117.     // Print circle
  118.     friend std::ostream& operator << ( std::ostream& s, const Circle& C )  {
  119.       s << "Center: " << C.getC() << ", r = " << C.getR();
  120.       return s;
  121.     }
  122. private:
  123.     // radius
  124.     double r;
  125.     // center
  126.     Point2d c;
  127.  
  128. };
  129.  
  130. void kveta(double RR1,double XX1,double YY1,double RR2,double XX2,double YY2,double &A,double &B)
  131. {
  132.     Circle c1(RR1, XX1, YY1);
  133.     Circle c2(RR2, XX2, YY2);
  134.     Point2d i1, i2;
  135.  
  136.     size_t i_points = c1.intersect(c2, i1, i2);
  137.  
  138.     A=i1.x();
  139.     B=i1.y();
  140.  
  141.     return;
  142. }
  143.  
  144. double X[7],Y[7],R[7];
  145.  
  146. bool good(){
  147.  
  148.          for (int i=1;i<=3;i++)
  149.           for (int j=i+1;j<=4;j++)
  150.            if (   ( X[i]-X[j] )*( X[i]-X[j] ) + ( Y[i]-Y[j] )*( Y[i]-Y[j] ) <(R[i]+R[j])*(R[i]+R[j]) ) return false;
  151.            return true;
  152. }
  153.  
  154.  
  155. bool check(double z){
  156.  
  157.     double A,B;
  158.           X[1]=0; Y[1]=R[1];
  159.  
  160.       kveta(0,R[1],R[1]+R[2], 0,z,z-R[2], A,B);
  161.       X[2]=A; Y[2]=B;
  162.  
  163.       kveta(X[2],Y[2],R[2]+R[3], 0,z,z-R[3],A,B);
  164.       X[3]=A; Y[3]=B;
  165.  
  166.       kveta(X[3],Y[3],R[3]+R[4], 0,z,z-R[4],A,B);
  167.       X[4]=A; Y[4]=B;
  168.  
  169.       return good();
  170.  
  171. }
  172.  
  173. main()
  174. {
  175.  
  176.          cin>>R[1]>>R[2]>>R[3]>>R[4];
  177.           R[1]/=2; R[2]/=2; R[3]/=2; R[4]/=2;
  178.  
  179.           sort   (R+1,R+5);
  180.           reverse(R+1,R+5);
  181.  
  182.  
  183.  
  184.           int le=2*(R[1]+R[2]),ri= 34142,ans;
  185.           double mid;
  186.  
  187.            while (le<=ri)
  188.            {
  189.                  mid=(int)((le+ri)/2);
  190.                  if (check((double)1.00*(double)mid/2)) {ans=mid; ri=mid-1;} else le=mid;
  191.            }
  192.            cout<<ans<<endl;
  193.  
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement