UVA Problem 438 – The Circumference of the Circle Solution

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

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;
}

UVA Problem 417 – Word Index Solution

UVA Problem 417 – Word Index Solution:


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

Solving Technique:

This one of the worst code I have ever written. It is both slow and wastes huge amount of memory, but still works. I am sharing this code as an example 5 dimensional re-sizable (vector) array. There are far far far better solution than this, so I won’t explain it.

If the input is thought of as string, then for each position the character right to current character is at least current character plus one. Since there are 5 length classes 1,2,3,4,5. So for each of them I applied this logic.

 

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:

26
1
0
83681

 


Output:

z
a
cat
vwxyz

Code:

/**
 * Author:    Asif Ahmed
 * site:      quickgrid.wordpress.com
 * Problem:   UVA 417 - word index
 * Technique: Very Slow and worst possible solution.
 *            5 (five) dimensioanl vector integer array. 1, 2
 *            3, 4 (four) dimensional integer array.
 */

#include <vector>
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;


#define N 26


int main() {


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


    vector<vector<vector<vector<vector<int> > > > > array5d;


      array5d.resize(N);
      for (int i = 0; i < N; ++i) {
        array5d[i].resize(N);

        for (int j = 0; j < N; ++j){
          array5d[i][j].resize(N);

            for (int k = 0; k < N; ++k){
              array5d[i][j][k].resize(N);

                for (int m = 0; m < N; ++m){
                  array5d[i][j][k][m].resize(N);
                }

            }
        }

      }

        int s1[N];
        int s2[N][N];
        int s3[N][N][N];
        int s4[N][N][N][N];
        int n = 0;


        for(int i = 0; i < N; ++i)
            s1[i] = ++n;



        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                s2[i][j] = ++n;

            }
        }



        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){

                        s3[i][j][k] = ++n;

                }
            }
        }




        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){
                    for(int m = k + 1; m < N; ++m){

                        s4[i][j][k][m] = ++n;

                    }
                }
            }
        }




        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){
                    for(int m = k + 1; m < N; ++m){
                        for(int t = m + 1; t < N; ++t){

                            array5d[i][j][k][m][t] = ++n;

                        }

                    }
                }
            }
        }




        char input[N];

        while( gets(input) ){

            int len = strlen(input);

            switch(len){
            case 1:
                printf("%d\n", s1[ input[0] - 'a' ] );
                break;
            case 2:
                printf("%d\n", s2[ input[0] - 'a' ][ input[1] - 'a' ] );
                break;
            case 3:
                printf("%d\n", s3[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ] );
                break;
            case 4:
                printf("%d\n", s4[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ][ input[3] - 'a' ] );
                break;
            case 5:
                printf("%d\n", array5d[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ][ input[3] - 'a' ][ input[4] - 'a' ] );
                break;
            }

       }



  return 0;
}

UVA Problem 11716 – Digital Fortress Solution

UVA Problem 11716 – Digital Fortress Solution:


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

Solving Technique:

This is an easier string problem. The task is to arrange the characters within the string in a certain order.

If the input string length is not square of a number then print INVALID. Ex: “DAVINCICODE” has length of 11. Squaring no number results in 11.

“DTFRIAOEGLRSI TS” has length of 16 including the space character. Square root of 16 is 4 and 4 * 4 is 16. So this is valid input.

Now if the input is valid then next task is to rearrange them. Instead of following given solution technique in the question it can solved much faster in another way. Following instruction in the question gives intuition that first the string must be positioned on 2 dimensional matrix in row major order. Then traverse them column by column.

A better way is find out each group length from square rooting the original string length. Next starting from first group take a character then skip by group length to get next column major character. After its done do this from the next character of first group.


Visualization:
uva 11716 rearrange string in column major order
uva 11716 rearrange string in column major order

 

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:

3
WECGEWHYAAIORTNU
DAVINCICODE
DTFRIAOEGLRSI TS

 


Output:

WEAREWATCHINGYOU
INVALID
DIGITAL FORTRESS

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11716 - Digital Fortress
 * Technique: Square String Traverse from row major
 *            to column major by skipping.
 */

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


#define N 10002
static char s[N];
static char output[N];


int main(){

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


    int n;
    scanf("%d", &n);
    getchar();


    while( n-- ){
        gets(s);


        // Get the length of string and length of each string group.
        int len = strlen(s);
        int rc = sqrt(len);


        // Reset in case there are characters from previous iteration.
        memset(output, 0, sizeof output);



        // If the string length can be divided into equal parts
        // then traverse by skipping certain length.
        if( rc * rc == len ){

            int k = 0;

            for( int j = 0; j < rc; ++j ){
                for( int i = j; i < len; i = i + rc ){
                    output[k++] = s[i];
                }
            }

            puts(output);

        }
        else{
            puts("INVALID");
        }

    }


    return 0;
}

N Queen Visualizer Sample Java Program

Explanation:

TODO.

This is just a sample program for anyone trying to implement their own version of N Queen Visualizer. This may be modified to create animation for other problems such as knight’s tour.

This version doesn’t have much. Blue cells represent empty / non traversed cells. White cells represent traversed but backtracked from that cell to another cell meaning its not part of Solution. Finally orange cells represent solutions.

The theory and code is explained here in geeksforgeeks.

Get the newest code from my github [TODO] code repository. I will update it eventually.

App Screenshots:

java n queen solver animation screenshot
java n queen solver animation screenshot

N Queen Code:

/**
 * Author:      Asif Ahmed
 * Site:        https://quickgrid.wordpress.com
 * Description: N Queen visualizer Sample.
 */

import javax.swing.*;
import java.awt.*;

/**
 * Created by computer science on 12/6/2015.
 */
public class App {

    final static int M = 8;
    static JLabel [][] jLabel = new JLabel[M][M];


    static int board[][] = new int[M][M];


    static void printSolution(){

        for(int i = 0; i < M; ++i){
            for(int j = 0; j < M; ++j){
                System.out.printf("%d ", board[i][j]);
            }
            System.out.printf("\n");
        }

    }


    static boolean isSafe( int row, int col ) {

        try {
            Thread.sleep(20);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        for (int i = 0; i < col; ++i)
            if (board[row][i] == 1)
                return false;


        for (int i = row, j = col; i >= 0 && j >= 0; --i, --j) {

            if (board[i][j] == 1)
                return false;

        }

        for (int i = row, j = col; i < M && j >= 0; ++i, --j){

            if (board[i][j] == 1)
                return false;
         }

        return true;
    }



    static boolean findSolution( int col ){

        if(col >= M)
            return true;


        for( int i = 0; i < M; ++i ){

            //Increase the sleep value to slow down the animation
            try {
                Thread.sleep(0);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            if( isSafe( i, col) == true ){

                board[i][col] = 1;
                jLabel[i][col].setBackground(Color.ORANGE);


                if( findSolution( col + 1) == true )
                    return true;


                board[i][col] = 0;
                jLabel[i][col].setBackground(Color.WHITE);

            }

        }


        return false;

    }

    static void solveNQueen(){



        try {
            Thread.sleep(500);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }


        // reset board
        for(int i = 0; i < M; ++i) {
            for (int j = 0; j < M; ++j) {

                try {
                    Thread.sleep(20);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                board[i][j] = 0;
                jLabel[i][j].setBackground(Color.BLUE);
            }
        }



        //If solution exist print otherwise show error message
        if( findSolution( 0 ) == false )
            System.out.println("No Solution.\n");
        else
            printSolution();

    }




    App() {


        JFrame jFrame = new JFrame("NQueen Visualizer.");

        jFrame.setLayout(new GridLayout(M, M));
        jFrame.setSize(400, 400);

        jFrame.setDefaultCloseOperation(jFrame.EXIT_ON_CLOSE);


        for(int i = 0; i < M; ++i) {
            for (int j = 0; j < M; ++j) {
                jLabel[i][j] = new JLabel( "(" + i + "," + j + ")" );
                jLabel[i][j].setHorizontalAlignment(SwingConstants.CENTER);

                jLabel[i][j].setSize(50, 50);

                jLabel[i][j].setOpaque(true);

                //Random rand = new Random();
                //jLabel[i].setBackground(new Color(rand.nextFloat(), rand.nextFloat(), rand.nextFloat()));

                jFrame.add(jLabel[i][j]);
            }
        }


        jFrame.setVisible(true);

    }






    public static  void main( String args[] ){

        SwingUtilities.invokeLater(new Runnable() {
            @Override
            public void run() {
                new App();
            }
        });

        solveNQueen();

    }

}