Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <algorithm>
- #include <iostream>
- #include <stdio.h>
- #include <cmath>
- using namespace std;
- #ifndef max
- #define max(a,b) (((a) > (b)) ? (a) : (b))
- #endif
- #ifndef min
- #define min(a,b) (((a) < (b)) ? (a) : (b))
- #endif
- /*
- * Find the intersection point(s) of two circles,
- * when their centers and radiuses are given (2D).
- */
- class Point2d{
- public:
- Point2d() {}
- Point2d(double x, double y)
- : X(x), Y(y) {}
- double x() const { return X; }
- double y() const { return Y; }
- /**
- * Returns the norm of this vector.
- * @return the norm
- */
- double norm() const {
- return sqrt( X * X + Y * Y );
- }
- void setCoords(double x, double y) {
- X = x; Y = y;
- }
- // Print point
- friend std::ostream& operator << ( std::ostream& s, const Point2d& p ) {
- s << p.x() << " " << p.y();
- return s;
- }
- private:
- double X;
- double Y;
- };
- class Circle{
- public:
- /**
- * @param R - radius
- * @param C - center
- */
- Circle(double R, Point2d& C)
- : r(R), c(C) {}
- /**
- * @param R - radius
- * @param X - center's x coordinate
- * @param Y - center's y coordinate
- */
- Circle(double R, double X, double Y)
- : r(R), c(X, Y) {}
- Point2d getC() const { return c; }
- double getR() const { return r; }
- size_t intersect(const Circle& C2, Point2d& i1, Point2d& i2) {
- // distance between the centers
- double d = Point2d(c.x() - C2.c.x(),
- c.y() - C2.c.y()).norm();
- // find number of solutions
- if(d > r + C2.r) // circles are too far apart, no solution(s)
- {
- std::cout << "Circles are too far apart\n";
- return 0;
- }
- else if(d == 0 && r == C2.r) // circles coincide
- {
- std::cout << "Circles coincide\n";
- return 0;
- }
- // one circle contains the other
- else if(d + min(r, C2.r) < max(r, C2.r))
- {
- std::cout << "One circle contains the other\n";
- return 0;
- }
- else
- {
- double a = (r*r - C2.r*C2.r + d*d)/ (2.0*d);
- double h = sqrt(r*r - a*a);
- // find p2
- Point2d p2( c.x() + (a * (C2.c.x() - c.x())) / d,
- c.y() + (a * (C2.c.y() - c.y())) / d);
- // find intersection points p3
- i1.setCoords( p2.x() + (h * (C2.c.y() - c.y())/ d),
- p2.y() - (h * (C2.c.x() - c.x())/ d)
- );
- i2.setCoords( p2.x() - (h * (C2.c.y() - c.y())/ d),
- p2.y() + (h * (C2.c.x() - c.x())/ d)
- );
- if(d == r + C2.r)
- return 1;
- return 2;
- }
- }
- // Print circle
- friend std::ostream& operator << ( std::ostream& s, const Circle& C ) {
- s << "Center: " << C.getC() << ", r = " << C.getR();
- return s;
- }
- private:
- // radius
- double r;
- // center
- Point2d c;
- };
- void kveta(double RR1,double XX1,double YY1,double RR2,double XX2,double YY2,double &A,double &B)
- {
- Circle c1(RR1, XX1, YY1);
- Circle c2(RR2, XX2, YY2);
- Point2d i1, i2;
- size_t i_points = c1.intersect(c2, i1, i2);
- A=i1.x();
- B=i1.y();
- return;
- }
- double X[7],Y[7],R[7];
- bool good(){
- for (int i=1;i<=3;i++)
- for (int j=i+1;j<=4;j++)
- 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;
- return true;
- }
- bool check(double z){
- double A,B;
- X[1]=0; Y[1]=R[1];
- kveta(0,R[1],R[1]+R[2], 0,z,z-R[2], A,B);
- X[2]=A; Y[2]=B;
- kveta(X[2],Y[2],R[2]+R[3], 0,z,z-R[3],A,B);
- X[3]=A; Y[3]=B;
- kveta(X[3],Y[3],R[3]+R[4], 0,z,z-R[4],A,B);
- X[4]=A; Y[4]=B;
- return good();
- }
- main()
- {
- cin>>R[1]>>R[2]>>R[3]>>R[4];
- R[1]/=2; R[2]/=2; R[3]/=2; R[4]/=2;
- sort (R+1,R+5);
- reverse(R+1,R+5);
- int le=2*(R[1]+R[2]),ri= 34142,ans;
- double mid;
- while (le<=ri)
- {
- mid=(int)((le+ri)/2);
- if (check((double)1.00*(double)mid/2)) {ans=mid; ri=mid-1;} else le=mid;
- }
- cout<<ans<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement