UVA Problem 438 – The Circumference of the Circle Solution

UVA Problem 438 – The Circumference of the Circle Solution:

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 10347 – Medians Solution

UVA Problem 10347 – Medians Solution:

Solving Technique:

This is a simple geometrical problem. We can use Heron’s formula to calculate the area.

Use double for safety. Print 3 places after decimal point. If the area is invalid then print -1.000 ( with 3 Zeros ) after decimal point. This may be a reason for WA.

I have provided two codes. One of them uses fread and string stream ( include sstream ) to take and process input. I have commented this code for easier understanding. The other code is with out fread, stringstream and not commented.

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.

Critical Inputs:

``` 1  2  3
5  9  4
3  2  3
4  5  3
-3 -3 -3```

Output:

```-1.000
-1.000
3.771
8.000
5.196```

Code:

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cmath>

static char buffer[32768];

int main(){
double a,b,c,s;

/**
* @brief Read file from stdin and create string stream of buffer
*/
std::stringstream ss(buffer);

while (ss >> a >> b >> c){

/**
* Heron's Formula: s, is semi perimeter
*/
s = (a + b + c) / 2.0;

/**
* Heron's Formula: area, of a triangle
*/
double area = (4.0 / 3.0) * sqrt(s * (s - a) * (s - b) * (s - c));

/**
* If area is not valid then print -1, otherwise print area
*/
area > 0 ? printf("%0.3lf\n", area) : printf("-1.000\n");
}
return 0;
}
```

Code ( Without fread() and stringstream() ):

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cmath>

using namespace std;

int main(){
double a,b,c,s;

while (scanf("%lf%lf%lf", &a, &b, &c) == 3){

double s = (a + b + c) / 2.0;
double area = (4.0 / 3.0) * sqrt(s * (s - a) * (s - b) * (s - c));

if(area > 0)
printf("%0.3lf\n", area);
else
printf("-1.000\n");

}
return 0;
}
```