IT/소스코드

Intersecting Circles

zzun 2004. 6. 15. 05:12
반응형
http://online-judge.uva.es/p/v4/453.html

/**

Intersecting Circles

zzun
http://zzun.net

**/

#include <fstream.h>
#include <math.h>
#include <stdio.h>

float pow2( float a )
{
       return pow( a, 2 );
}

int main()
{
       ifstream fin;
       float a[2], b[2], r[2], x[2], y[2], temp;

       fin.open( "test.in" );

       fin >> a[0] >> b[0] >> r[0] >> a[1] >> b[1] >> r[1];

       while ( ! fin.eof() )
       {
               float d = sqrt( pow2(a[0]-a[1]) + pow2(b[0]-b[1]) );        // distance

               if ( a[0]==a[1] && b[0]==b[1] && r[0]==r[1] )
                       printf( "THE CIRCLES ARE THE SAME\n" );

               else if ( d>r[0]+r[1] || d<fabs(r[0]-r[1]) )
                       printf( "NO INTERSECTION\n" );

               else if ( d == r[0]+r[1] )        // circumscription
               {
                       x[0] = ( r[0]*a[1] + r[1]*a[0] ) / ( r[0] + r[1] );
                       y[0] = ( r[0]*b[1] + r[1]*b[0] ) / ( r[0] + r[1] );
                       printf( "(%.3f,%.3f)\n", x[0], y[0] );
               }

               else if ( d == fabs(r[0]-r[1]) )        // inscription
               {
                       x[0] = ( r[0]*a[1] - r[1]*a[0] ) / ( r[0] - r[1] );
                       y[0] = ( r[0]*b[1] - r[1]*b[0] ) / ( r[0] - r[1] );
                       printf( "(%.3f,%.3f)\n", x[0], y[0] );
               }

               else if ( a[0] == a[1] )        // same a, diff b
               {
                       y[0] = ( (b[0]+b[1]) - (r[0]+r[1])*(r[0]-r[1])/(b[0]-b[1]) ) / 2;
                       temp = sqrt( (r[0]-y[0]+b[0])*(r[0]+y[0]-b[0]) );
                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", a[0]-temp, y[0], a[0]+temp, y[0] );
               }

               else if ( b[0] == b[1] )        // same b, diff a
               {
                       x[0] = ( (a[0]+a[1]) - (r[0]+r[1])*(r[0]-r[1])/(a[0]-a[1]) ) / 2;
                       temp = sqrt( (r[0]-x[0]+a[0])*(r[0]+x[0]-a[0]) );
                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", x[0], b[0]-temp, x[0], b[0]+temp );
               }

               else        // normal case
               {
                       float ef[3], A, B, C;

                       B = 2 * (b[1]-b[0]);
                       A = 2 * (a[1]-a[0]) / B;
                       C = ( (a[0]+a[1])*(a[0]-a[1]) + (b[0]+b[1])*(b[0]-b[1]) - (r[0]+r[1])*(r[0]-r[1]) ) / B;

                       ef[0] = 1 + pow2(A);
                       ef[1] = 2*b[0]*A - 2*a[0] + 2*A*C;
                       ef[2] = pow2(C) + 2*b[0]*C + pow2(a[0]) + pow2(b[0]) - pow2(r[0]);

                       temp = sqrt( pow2(ef[1]) - 4*ef[0]*ef[2] );        // b^2 - 4ac
                       x[0] = (temp*(-1) - ef[1]) / (2*ef[0]);
                       x[1] = (temp - ef[1]) / (2*ef[0]);

                       for (int i=0; i<2; i++)
                               y[i] = (-1)*C - A*x[i];

                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", x[0], y[0], x[1], y[1] );
               }

               fin >> a[0] >> b[0] >> r[0] >> a[1] >> b[1] >> r[1];
       }

       fin.close();

       return 0;
}


[test.in]
0.0 0.0 1.0
3.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
1.0 0.0 1.0
5.6 6.6 3.2
3.2 4.8 3.5
5.0 5.0 5.0
0.0 0.0 5.0
0.0 0.0 1.0
3.0 0.0 2.0
0.0 0.0 3.0
2.0 0.0 1.0
3.5 8.6 6.3
3.5 0.3 4.2
0.0 0.0 5.0
1.0 0.0 2.0



> time ./n04_circle
NO INTERSECTION
THE CIRCLES ARE THE SAME
(0.500,-0.866)(0.500,0.866)
(2.880,8.285)(6.456,3.517)
(0.000,5.000)(5.000,0.000)
(1.000,0.000)
(3.000,0.000)
(0.389,3.122)(6.611,3.122)
NO INTERSECTION
0.000u 0.000s 0:00.00 0.0%      0+0k 0+0io 164pf+0w
반응형