UVA Problem 438 – The Circumference of the Circle Solution

Posted on by quickgrid

UVA Problem 438 – The Circumference of the Circle Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

Given three points find the circumference of the circle. Points are non-collinear meaning they are not on a straight line.

Have a look at Circumscribed circle, Semi perimeter and Heron’s formula to find more about the formula and derivation.

Also related to this have a look at UVA 10432 – Polygon Inside a Circle.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

0.0 -0.5 0.5 0.0 0.0 0.5
0.0 0.0 0.0 1.0 1.0 1.0
5.0 5.0 5.0 7.0 4.0 6.0
0.0 0.0 -1.0 7.0 7.0 7.0
50.0 50.0 50.0 70.0 40.0 60.0
0.0 0.0 10.0 0.0 20.0 1.0
0.0 -500000.0 500000.0 0.0 0.0 500000.0

 

Output:

3.14
4.44
6.28
31.42
62.83
632.24
3141592.65

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 438 - The Circumference of the Circle.
 * Technique: Finding diameter and circumference of Circumscribed
 *            circle or Circumcircle.
 *            Using Heron's formula to calculate semi perimeter
 *            and area of triangle from Three points.
 */

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


#define PI 3.141592653589793


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    double x1, y1;
    double x2, y2;
    double x3, y3;


    while( scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3 ) == 6 ){

        // a dist between (x1,y1) and (x2,y2)
        // b dist between (x2,y2) and (x3,y3)
        // c dist between (x3,y3) and (x1,y1)

        double a = sqrt( pow(x1 - x2, 2) + pow(y1 - y2, 2) );
        double b = sqrt( pow(x2 - x3, 2) + pow(y2 - y3, 2) );
        double c = sqrt( pow(x3 - x1, 2) + pow(y3 - y1, 2) );


        // semi perimeter, s = (a+b+c)/2

        double s = ( a + b + c ) / 2;


        // Area using Heron's Formula

        double A = sqrt( s*(s-a)*(s-b)*(s-c) );


        // Diameter of circumscribed circle d = abc/2A

        double d = (a * b * c) / (2 * A);


        // Result circumference of the circumcircle or circumscribed circle

        double circumference = PI * d;


        printf("%.2lf\n", circumference );

    }


    return 0;
}

Unnecessary Complex Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 438 - The Circumference of the Circle.
 * Technique: Point and Line representation in structure.
 *            Finding diameter and circumference of Circumscribed
 *            circle or Circumcircle.
 *            Using Heron's formula to calculate semi perimeter
 *            and area of triangle from Three points.
 */

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


#define PI 3.141592653589793


struct Point{
    double x;
    double y;
};


struct Line{
    Point a;
    Point b;

    Point setPoints( Point _a = {0.0,0.0}, Point _b = {0.0,0.0} ){
        a = _a;
        b = _b;
    }

    double length(){
        return sqrt( pow(a.x - b.x, 2) + pow(a.y - b.y, 2) );
    }

};


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    Point point[3];
    Line  line [3];


    while( scanf("%lf%lf%lf%lf%lf%lf", &point[0].x, &point[0].y, &point[1].x, &point[1].y, &point[2].x, &point[2].y ) == 6 ){


        // Loop is same as code below.
        //line[0].setPoints(point[0], point[1]);
        //line[1].setPoints(point[1], point[2]);
        //line[2].setPoints(point[2], point[0]);

        int N = 3;
        for( int i = 0; i < N; ++i )
            line[i].setPoints( point[i], point[(i+1) % N] );



        // semi perimeter is half of perimeter.
        // Perimeter is distance around the shape in 2D.

        double s = ( line[0].length() + line[1].length() + line[2].length() ) / 2;


        // Area using Heron's Formula

        double A = sqrt( s * (s - line[0].length()) * (s - line[1].length()) * (s - line[2].length()) );


        // Diameter of circumscribed circle d = abc/2A

        double d = (line[0].length() * line[1].length() * line[2].length()) / (2 * A);


        // Result circumference of the circumcircle

        double circumference = PI * d;


        printf("%.2lf\n", circumference );

    }


    return 0;
}

UVA Problem 10432 – Polygon Inside A Circle Solution

Posted on by quickgrid

UVA Problem 10432 – Polygon Inside A Circle Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

This is a rather easy geometry / computational geometry problem. Given the radius of a Circumscribed circle and count of sides of a polygon the task is to find the area of the polygon. A Circumscribed circle is a circle that passes through all vertices of a plane figure and contains the entire figure in its interior.

The formula below can be written into a single formula by combining all the formulas. More information and the combined formula can be found here.

Learn more about regular polygon here including the formula.

Visual Explanation:

I have tried to explain the concept below using figures. They are not drawn to scale. The small circles represent intersection point between polygon vertices and the circumscribed circle.

Circumcircle figure 1
Circumcircle figure 1
Circumcircle figure 2
Circumcircle figure 2
Circumcircle figure 3
Circumcircle figure 3
Example:

It is an example with radius, r = 2 and sides, n = 8.

Circumcircle figure 4 example
Circumcircle figure 4 example

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

2 2000
10 3000

 

Output:

12.566
314.159

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10432 - Polygon Inside A Circle
 * Technique: circumcircle Or, Isocele Area calculation.
 */

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


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    double r;
    int n;

    while( scanf( "%lf%d", &r, &n ) == 2 ){

        // Angle between each two points for every point.
        double PHI = ( double ) 360 / n ;

        // For each Isosceles in the polygon the angle between the base and radius.
        double THETA = (double) 90 - ( PHI / 2 );


        // Convert Degree angle to Radian to use in code.
        double THETA_RADIAN = THETA * M_PI / 180;


        //  a is base.
        double a = 2 * r * cos( THETA_RADIAN );

        // H is the height.
        double h = r * sin( THETA_RADIAN );

        // S represent Area of a single segment.
        double S = (a * h) / 2;


        // S * n is the are of complete polygon.
        printf("%.3lf\n",  S * n );


    }

    return 0;
}