Category: Algorithmic Problem

Solution 2: Algorithm 1

Below is the solution for Algorithm Problem 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define PI 3.14159265358979323846

float compute_comman_area(double r0,double r1,double x0,double y0,double x1,double y1){

     double c,CBA,CAB,CBD,CAD,Area;

     //length
     c = sqrt(pow((x1-x0),2) + pow((y1-y0),2));

     //IN RADIANS
     CBA = (acos((pow(r1,2) + pow(c,2) - pow(r0,2))/(2*r1*c)));
     CAB = (acos((pow(r0,2) + pow(c,2) - pow(r1,2))/(2*r0*c)));

     CBD = 2*CBA;
     CAD = 2*CAB;

     Area = (CBD*pow(r1,2) - pow(r1,2)*sin(CBD) + CAD*pow(r0,2) - pow(r0,2)*sin(CAD))/2;

     printf("%lf", CBA);

     return Area;
}

int main(){

    double r1=10,r0=10,x0=0,y0=0,x1=0,y1=10, Area, Area0;

    //getting input
    /*printf("Enter the radius of the first circle\nand the centre point");
    scanf("%lf%lf%lf",&r0,&x0,&y0);
    printf("Enter the radius of the first circle\nand the centre point");
    scanf("%lf%lf%lf",&r1,&x1,&y1);*/

    //calling function to compute area
    Area0 = PI * pow(r0, 2) + PI * pow(r1, 2);
    Area = Area0 - compute_comman_area(r0,r1,x0,y0,x1,y1);

    //printing the area
    printf("The area thus computed is:%lf",Area);

return 0;
}

You can download the source file here.

January 14, 2010

Solution Hint: Algorthimic Problem 1st (How to find the shared area of two intersected circle)
Algorithm Green Image

If you will go for the problem statement then you will find that you have to find the Area covered by intersection of two or three circles and the coordinates and radius is given.

Lets see how to find the shared area between intersection of two circles.

Let two circles are given.
```
1. center(x0,y0), radius (r0)
 2. center(x1,y1), radius (r1)
```
Let A be the centre of the circle ( x0, y0 ) and B be the centre of the other circle ( x1,y1 ).

Draw the circles with appropriate radii r0 and r1 so that there is a reasonable amount of overlap. The length AB is calculated from the coordinates of the centre:
```
AB = sqrt{(x1-x0)^2 + (y1-y0)^2}
```
For convenience let this length be denoted by c.

The two circles intersect in two points which I will label C and D.

Now we must calculate the angles CAD and CBD, and we do this using the cosine formula. In fact it is half of these angles that we first calculate, using triangle CAB.
```
r0^2 = r1^2 + c^2 - 2*r1*c*cos(CBA)
```
```
cos(CBA) = (r1^2 + c^2 - r0^2)/(2*r1*c)
```
found CBA, then CBD = 2(CBA).

Similarly,
cos(CAB) = (r0^2 + c^2 - r1^2)/(2*r0*c)
and then
CAD = 2(CAB)

Express CBD and CAD in radian measure. Then we find the segment of each of the circles cut off by the chord CD, by taking the area of the sector of the circle BCD and subtracting the area of triangle BCD.
Similarly we find the area of the sector ACD and subtract the area of triangle ACD.
```
Area = ( 1/2 )( CBD ) r1 ^ 2 - ( 1/2 ) r1 ^ 2 * sin( CBD )
  + ( 1/2 )( CAD ) r0 ^ 2 - ( 1/2 ) r0 ^ 2 * sin( CAD )
```
Remember that for the area of the sectors you must have CBD and CAD in radians.

One more thing if the two circles are of the SAME radius please note that the area is symmetrical about the chord CD. Therefore, you only need to find the area in one half of the intersection and multiply by 2.

A shorter equation is

Area = 2 * ( ( 1/2 ) ( CBD ) r1 ^ 2 - ( 1/2 ) r1 ^ 2.sin( CBD ) ).

One more derivation if the redis is equal then you can find out using, this formula
Area = r^2*(q - sin(q)) where q = 2*acos(c/2r),
where c = distance between centers and r is the common radius.

I think now you can solve this. If something goes wrong, then post in the comments.
January 9, 2010
Algorithm Problem 2: Easy

Algorithm Problem Solution

Hey, try to solve this. This is an easy problem to solve.

Problem Level: Easy

Problem Statement:

A palindrome is a word, number, or phrase that reads the same forwards as backwards. For example, the name “anna” is a palindrome. Numbers can also be palindromes (e.g. 151 or 753357).

Additionally numbers can of course be ordered in size. The first few palindrome

numbers are: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, …

The number 10 is not a palindrome (even though you could write it as 010) but a zero as leading digit is not allowed.

Input:

The input consists of a series of lines with each line containing one integer value i (1 ≤ i ≤2*109).

This integer value i indicates the index of the palindrome number that is to be written to the output, where index 1 stands for the first palindrome number (1), index 2 stands for the second palindrome number (2) and so on. The input is terminated by a line containing 0.

Output:

For each line of input (except the last one) exactly one line of output containing a single (decimal) integer value is to be produced. For each input value i the i-th palindrome number is to be written to the output.

Sample Input Output for Sample Input

1 1
12 33
24 151

December 20, 2009
Algorithm Problem 1 : Med

Algorithm Problem

This problem I got to solve on “Prodyogiki 09” in an University Competition of NITs. I was unable to solve that. Try to solve this.

Problem Level: Med

Problem statement: The world is at war. The machine have vowed to clear the human race and the human have determined to make machine extinct. You have been elected as leader of resistance. You need to destroy the Cyberdyne systems. In a bid to do so, u have launched an air attack on Cyberdine. This tasks is, like so many things, best accomplished by randomly blowing things up. Fortunately, you have a proven talent in this area.

Even as we speak, your warplanes are dropping large bombs all over the machines. You need some way to determine the extent of the carnage. If the pilots have served you well, they may live for another precious day. You don’t really care about the property damage or the massive casualties. As such, all you want to know is the total area of devastation. Every bomb has a destruction radius. Anything within that radius is completely eradicated. Computing the area for one bomb is fairly simple, but for many it isn’t quite so easy. However, your human friends have surprisingly large proportion of skilled programmers, so you have respectfully requested their assistance. The survivors of this request (ie, those who cooperated) are now hard at work, writing a program to solve this problem…

Input

Input consists of a number of cases. Each case lists all of the bombs dropped on one day of your rule. The first line of case contains n, the number of bombs. The next n lines each contain the x and y coordinates where one bomb exploded, and its destruction radius. There will be at most 100 bombs. Coordinates given are real numbers between 0 and 100, and the radius is a real number between 0 and 10.

There will be at most 50 cases. The last day of bombing will be followed by a line containing 0. This case must not be processed.

Output

For each case, output the area of destruction from all of the bombs from that day, accurate to three decimal places.

Sample Input Output for Sample Input

1
0 0 10 314.159

2
0 0 10
0 10 10 505.482

December 13, 2009

Category: Algorithmic Problem

Solution 2: Algorithm 1

Solution Hint: Algorthimic Problem 1st (How to find the shared area of two intersected circle)

Algorithm Problem 2: Easy

Algorithm Problem 1 : Med