Lightoj 1331 solution in English

 

Lightoj 1331 Ajent J 

Problem Link

Click here to see the discussion in Bangla

In the movie Dhoom 2, Hrithik Roshan’s diamond theft scene is quite famous. Similarly, LightOJ problem 1331 is about a diamond theft.

                                          

Here we have an agent ‘J’ who wants to steal the diamond kept in a museum. But the theft isn’t that easy, because there are three circular laser scanners, continuously rotating.

These three circles are placed in such a way that each circle is externally tangent to the other two, and the diamond is placed in the middle enclosed region.

Our task is to find the area of that enclosed region (the shaded diamond-shaped area). The radii of the three circles are given: $R1, R2, R3$.

                                     

Step 1: Forming the Triangle

If we connect the centers of the three circles, we form a triangle.

• The distance between the centers of circle $R1$ and $R2$:

  $$a = R1 + R2$$

• The distance between the centers of circle $R2$ and $R3$:

  $$b = R2 + R3$$

• The distance between the centers of circle $R1$ and $R3$:

  $$c = R1 + R3$$

Step 2: Area of the Triangle

Once we have the three sides $a, b, c$, we can calculate the area of the triangle using Heron’s formula.

First compute the semi-perimeter:

$$s = \frac{a+b+c}{2}$$

Then, the triangle’s area is:

$$\text{Area}_{\triangle} = \sqrt{s(s-a)(s-b)(s-c)}$$

Step 3: Sector Areas (Circular Arcs)

                                              

From basic geometry, we know that the area of a circular sector is:

$$\text{Sector Area} = \tfrac{1}{2} r^2 \theta$$

where $r$ is the circle’s radius and $\theta$ is the angle in radians subtended at the circle’s center.

So, to compute the circular sectors inside the triangle, we need the angles of the triangle at the vertices.

Using the cosine rule:

$$\cos(C) = \frac{a^2 + b^2 - c^2}{2ab}$$ $$\cos(A) = \frac{b^2 + c^2 - a^2}{2bc}$$ $$\cos(B) = \frac{c^2 + a^2 - b^2}{2ca}$$

Now, the sector areas are:

$$\text{Area}_1 = \tfrac{1}{2} R1^2 \cdot \arccos\left(\frac{c^2 + a^2 - b^2}{2ca}\right)$$ $$\text{Area}_2 = \tfrac{1}{2} R2^2 \cdot \arccos\left(\frac{b^2 + a^2 - c^2}{2ab}\right)$$ $$\text{Area}_3 = \tfrac{1}{2} R3^2 \cdot \arccos\left(\frac{c^2 + b^2 - a^2}{2bc}\right)$$

Step 4: The Diamond Area

Finally, the required shaded region (diamond area) is:

$$\text{Diamond Area}={\text{Area}}_{\mathrm{△}}-({\text{Area}}_1+{\text{Area}}_2+{\text{Area}}_3)$$
For source code: Source code