Ciel and Map

Problem Link : http://www.codechef.com/problems/CIELMAP/

Idea : Given some point N . You have to find out the larger side of a quadrilateral that can be formed by 4 out of N point . The boundary of the quadrilateral may not be crossed by itself .

If N>4 , our answer is the distance between the farthest couple of points .
It can be determined using loop .

If N=4 , then we have to face the calculation for possible all quadrilateral .
For possible all permutation , we have to calculate two thing -

1. Whether the quadrilateral cross its own boundary or not .
2. If yes , skip this quadrilateral .
   Else , take the maximum side for count .

We can easily find out 1st requirment using the concept of vector cross product .

If points are A,B,C and D.

If the sign of AB*AC and AC*AD are same , that means all points are consecutively clockwise or anti-clockwise and a valid quadrilateral is possible . Then calculate AB , BC , CD , AD and take the maximum value of side for counting .

My Solution

Lights

Problem Link : http://www.codechef.com/problems/LIGHT/

Idea : In this problem , we have to find out the maximum height where a plane can run totaly in light. The height must be remain among the 0 and 1000 , as problem statement says .  So we can easily find out the height doing binary search within the range of h=0 and h=1000 .
For each value , we have to cheak whether in that height the plane can run or not .
At first , we calculate the cut point of the line at a height , along with which line , the plane can run by each light . Given the half of an angle of each triangle . This is the way we can calculate the cut point with the help of trigonometric ratio of tangent .
Now we want to see that which points are consecutive .

if given L and R are in a region where the cut points are consecutive , our answer is true and otherwise not.

Following this formulation , we can find out the maximum height .

My Solution

Snape and Ladder

Problem Link : http://www.codechef.com/problems/SNAPE/

Idea : If B is the base , L is the left side and R is the right side of a triangle ;
Given B and L . You have to calculate the minimum and maximum value for R .
The value of R will be minimum , if the angle between  B and R is 90 degree .
Then it is a right angle triangle and we can easily calculate the value of R by pythagoras theorem .

 So  ,  R min = sqrt(L*L-B*B)

The value of R will be maximum , if the angle between  B and L is 90 degree .
Then it is a right angle triangle and we can easily calculate the value of R by pythagoras theorem .

 So  ,  R max = sqrt(L*L+B*B)

My Solution

Chef and the Cake I

Problem Link : http://www.codechef.com/problems/CAKE1AM/

Idea : We have to calculate the area that covers by two rectangle . Given the co-ordinate in 2D space . Our answer is the summation of the area of the two rectangle minus the area that they intersect , that also a rectangle . If we analyze some case , we can easily understand that their intersection rectangle's lower left corner is the maximum x co-ordinate and the maximum y co-ordinate of all the lower left points as wll as its upper right corner is the minimum x co-ordinate and the minimum y co-ordinate of all the upper right points . Tf the two point makes a rectangle , that means the two rectangle intersects . The two point makes a rectangle if the x and y co-ordinate of second point is larger than first .
Take input for co-ordinate of 4 points .

Add result the area made by the two rectangle . As shown below -

result+=(x2-x1)*(y2-y1)+(x4-x3)*(y4-y3)

If the rectangle intersects , subtract the area made by intersection rectangle from result . Show output .

My solution

Chef and The Right Triangles

Problem Link : http://www.codechef.com/problems/RIGHTRI/

Idea : Given co-ordinate of three vertex of a triangle in 2D space . You have to determine whether it is right triangle or not . If yes , Increase counter , because there are N triangle . A triangle is right triangle if and only if it satisfies the pythagoras theorem . If its largest side is c and other are a and b . Then the relation holds for all right triangle.
                c*c=a*a+b*b

Take input and calculate its sides . Find out its largest side and cheak the above condition and increase the counter if it is right triangle . One thing is important that , the sides are given by distance formula -

                Distance = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))

Here we do the sqrt operation and in condition cheaking part we are squaring it . It may occur floating point error . For that we calculate side by -

Distance = (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)

And our cheaking condition will be -

c=a+b.

The number of right triange is our answer .

My solution : http://pastebin.com/n6HhaFca

Circle of death

Problem Link : http://www.codechef.com/problems/CIRKILL/

Idea : Given N points , you have to take three points so that a unique circle can be formed . For other point , you have to count these point that is inside the circle or at the perimeter.
First take an int int pair to take point . Take input and store in a vector . Now there are how many ways to choose three point fron given N point ??? Obviously we can find out it with the help of loop . Now we should cheak whether a unique circle can be formed throw the three point or not . To do so , we can cheak the area of the triangle formed by the three points.
The formula to calculate area is-

             Area=x1*(y2-y3)+x2*(y3-y1)+x3(y1-y2)

If the area is not zero , that means a circle can be formed.

Now for other points , we have to count these point that is  inside the circle or at the perimeter. Now a determinant -

| (x² + y²)  x   y  1 |

| (x₁²+y₁²)  x₁  y₁  1 | = 0

| (x₂²+y₂²)  x₂  y₂  1 |

| (x₃²+y₃²)  x₃  y₃  1 |

given by the general circle equation of the three points and another point that we want to find out.

Now for all cases , solve the determinant . If its value is zero , that means the point is at perimeter of the circle and if the sign of the velue of the determinant is opposite to the area of the triangle , the point is inside the circle . So we got the number of occurning . Now the probablity of the number to all possible cases is our answer .

My Solution : http://pastebin.com/Sqw5PWpW

Closest Points

Problem Link : http://www.codechef.com/problems/CLOSEST

Although my solution for this problem is not good,i would like to share it with you.

Idea: Given N points as 3D for BTPD help center and Q points for banks.The problem want at least one correct solution fer accept :).In my solution,i calculate for first bank.Take input for N points in an array.Then take input for Q banks.Calculate distance from each help center to first bank.Find out the minimum one.Save the number of that help center that is closest to first bank.
Then show the same result for Q banks :)
My solution : http://pastebin.com/bUe1YDNS

Triangle From Centroid

Problem Link : http://www.spoj.com/problems/TRICENTR/

Idea: If distances from centroid to side a,b and c are ga,gb and gc respectively.
The height of the triangle is 3*ga , 3*gb and 3*gc. So we can calculate the area of the triangle easily by this formula-
           Area=a*ga*3/2                where,base is a and height is ga*3   
Now we have to calculate side b and c.
Look,we know the area of the triangle,the height of the triangle.It is quite simple to calculate side b and c.
            Area=b*gb*3/2.               where,base is b and height is gb*3
         So, b=(2*Area)/(3*gb)
 Similarly,  c=(2*Area)/(3*gc)
Now the radius of circumcircle is
R= (a*b*c)/(4*Area)
Distance from Orthocenter of the triangle to the center of the circumcircle of the triangle HO is-
HO=sqrt(9*R*R-a*a-b*b-c*c)
We know that,the distance from Orthocenter of the triangle to the centroid of the triangle HG is-
HG=2*HO/3

Our answer is Area and HG :)

My Solution : http://pastebin.com/mUyePC2u

Calculate the Area

 Problem Link : http://www.spoj.com/problems/CALCAREA/

 Idea: Given N points and we have to deduce the area of polygon made of given  points. First triangulate the polygon taking 3 points at a time.If the polygon is convex,  the summation of area of those triangles is the answer.Otherwise the answer is  the summation of area of those triangles whose points are convex in respect of the polygon minus summation of area of those triangles whose points are concave in respect of the polygon.
Take a vector of int int pair. Store the co-ordinate of given points in pair and push the pair in vector.Now,assume fixed the first point and make vector from first point to other point.Calculate the cross product taking couple of vector from first to other with the formula-
                  A*B=x1*y2-x2*y1.
So area of the triangle is A*B/2.
and add them.
You oppose that,all triangle are not part of the polygon,that means we should subtruct the area of concave triangles.See more specifically,if the triangle is concave to the polygon,the area given by the formula is positive else it is negative.Our convex area are negative and concave are positive.If we add them,we should get the required area.Of course take its absolute value.

My Solution:  http://pastebin.com/L9rgPBHB

Helping Lira

Problem Link : http://www.codechef.com/problems/HELPLIRA

Idea: For N triangle,Given the co-ordinates of three point for each.First calculate the area of each triangle and push in a vector.Take another vector and push in it the values of first vector. Sort second vector.Now we have minimum value at V2[0] and maximum value at V2[size-1].Our answers are the indexes of minimum value and maximum value in first vector.If there are multiple maximum or minimum value,we have to result for the last.For that,search maximum(Contained in V2[size-1]) and minimum (Contained in V2[0]) value in first vector from the last.If one if found,keep continue for another one.Then show output.

My Solution: http://pastebin.com/GFpyevR1