10386 - Circles in Triangle

[hr02]

I have no idea how to solve this kinds of problems, can anybody help me plz
thanks

[Mahbub]

The idea is pretty simple.

(I am saying only about 1st case as the cases are alike..)

First let the 'red line 1' is the connection between bottom right circle center to bottom left circle center. (horizontal line)

the red line 2 is the connection between bottom right circle center to top most circle center.


1. The angle formed by the red lines is 60 degree (hope u can get why )

2. U can find an equation from the bottom line three circles letting that
the angle formed between green and red (horizontal one ) is 'A' degree.
That is (r + r) cos (A) + .... = Side of triangle.

3. Similarly B = the other angle formed between red and green line.

But from 1 we get A+B = 60

Now u do a bin search!

After i get accepted i used even pre computed values for A & B which also get accepted..so u can omit runtime bin searching

Thanks
Light


Can anybody help me how to attach a figure in the reply!!![/quote][/b]

[Mahbub]

Sorry i forget to mention about the 'green line' in my prev reply

"The green Line is the connection between bottom right circle center to its left top tangent circle's center."

[hr02]

how can we find (r+r)cos(A)+....=side of triangle.
what is the full eqn?

[Mahbub]

Well..this is a liiltle odd for me to describe things without a figure..

If u had correctly assumed about the red and green line ..>

the side of trinagle = s;
s = 4 * (2r) * cos (A) + 2 * d

d = distance from the touch point of { bottom right circle with base of

triangle} to the right corner of the triangle .... (in f 2*ct root(3)*r)

for ur ezness:

the equation for binary search of A is :

2r + 2*(2rcos(60 - A)) + 2d = 4*(2r)*cos(A) + 2d;

LHS <=>
right side of triangle
= d + r + r + 2rCos(B) + 2rCos(B) + d /* B = 60 - A*/

RHS <=>
base of triangle
= d + 4 * (2rCos(A)) + d


And if u r not still Clear :

Code: Select all

/***********************/

#define PREC 1.0e-8

int main()
{  
	int N; 
	double pi,l,h,m,Y,r,s,m1,m2;

	pi = acos(-1.0);
	
	scanf("%d",&N);

	r = 1;
/*	l = pi * 24 / 180.0;
	h = pi * 25 / 180.0;

	while(h-l>=PREC)
	{
		m = (l + h)/2.0;

		Y = r + r*cos(pi/3.0 - m) - 2*r*cos(m);

		if(Y > 0.0)
		{
			h = m;
		}			
		else
		{
			l = m;
		}
	}
*/
		m2 = 0.43171784545542;

/*		l = pi * 43 / 180.0;
		h = pi * 44 / 180.0;

		while(h-l>=PREC)
		{
			m = (l + h)/2.0;

			Y = r + 2*r*cos(pi/3.0 - m) - 4*r*cos(m);

			if(Y > 0.0)
			{
				h = m;
			}			
			else
			{
				l = m;
			}
		}
*/

	m1 = 0.75435478480197;

	while(N--)
	{
		scanf("%lf",&r);

		s = 8*r*cos(m1) + 2*sqrt(3.0)*r;
		
		printf("%.10lf",s);		


		s = 2*r*sqrt(3.0) + 8*r*cos(m2);

		printf(" %.10lf\n",s);		
	}

	return 0;
}

[rakeb]

well i'v solved this problem by some simple math i.e. i calculated the value of a1 and a2 by doing some math

the eqn for the first triangle is

2cos(60-a1)+1- 4cos(a1)=0

=>2cos(60) cos(a1) + 2sin(60) sin(a1) + 1-4cos(a1) = 0

=>cos(a1) + 2sin(60) sin(a1) + 1 - 4cos(a1) = 0

=>2 * (sqrt(3)/2) sin(a1) - 3cos(a1) + 1 = 0

=>3 cos(a1) - sqrt(3) sin(a1)=1

=>sqrt(3) cos(a1) - sin(a1) = 1/sqrt(3)

=>{sqrt(3) / sqrt(4)} cos(a1) - {1 / sqrt(4)} sin(a1) =1 / (2sqrt(3))

=>{sqrt(3)/2} cos(a1) - {1/2} sin(a1) = 1 / (2sqrt(3))

=>cos(30) cos(a1) - sin(30) sin(a1) = 1 / (2sqrt(3))

=>cos(30+a1) = 1 / (2sqrt(3))

=>30 + a1 = acos(1 / (2sqrt(3))) //cos inverse

=>a1= acos(1/(2sqrt(3))) - 30

//all angles are in degree

in radian a1 wil be
a1= 0.7543...........somthing.... IN RADIAN

same way we can find a2 from the enq of second triangle