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