Tag: three

438 – The Circumference of the Circle

by MSiddeek, posted in Algorithms, Geometry, Problems

A circumcircle problem.
Given a triangle, find the circumference of its circumcircle. There’s an easy way and a hard way.
The hard way is to find the circle’s centre then calculate the radius. I used this solution for a previous problem. Code:

#include <iostream>
#include <complex>
#include <limits>
using namespace std;

typedef long double gtype;
#define equ(a, b, e) ( abs((a) - (b)) <= (e) )
const gtype len_before_point_digits = 1E6;
const gtype epsLen = numeric_limits<gtype>::epsilon() * len_before_point_digits;
const gtype pi = M_PI;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )
#define perp(p) ( point((p).y, -(p).x) )
#define intrN(a, b, p, q) ( crs((p)-(a),(b)-(a)) * (q) - crs((q)-(a),(b)-(a)) * (p) )
#define intrD(a, b, p, q) ( crs((p)-(a),(b)-(a)) - crs((q)-(a),(b)-(a)) )
#define circC(r) (2 * pi * abs(r))
#define plus(x) ((x) > 0 ? " + " : " - ")

int main() {
	point p[3], v[2][2], c;
	gtype r;
	cout.precision(2);
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
		// perp 1
		v[0][0] = 0.5l * (p[0] + p[1]);
		v[0][1] = perp(p[1] - p[0]) + v[0][0];
		// perp 2
		v[1][0] = 0.5l * (p[1] + p[2]);
		v[1][1] = perp(p[2] - p[1]) + v[1][0];
		// intersect
		gtype d = intrD(v[0][0], v[0][1], v[1][0], v[1][1]);
		if (!equ(d, 0, epsLen)) {
			c = intrN(v[0][0], v[0][1], v[1][0], v[1][1]) / d;
			r = abs(c - p[0]);
		} else
			r = 0;
		// out
		cout << fixed << circC(r) << endl;
	}
	return 0;
}

The easy way is to find the circumcircle’s radius through:

sin(\theta) = {a / 2 \over R} = {a \over 2 R}
And since:
area(ABC) = 1/2 \cdot b \cdot c \cdot sin(\theta)
area(ABC) = 1/2 \cdot b \cdot c \cdot {a \over 2 R}
R = a \cdot b \cdot c / (4 \cdot area(ABC))
This method is less prone to error. Implementation:

#include <iostream>
#include <complex>
#include <limits>
using namespace std;

typedef long double gtype;
const gtype pi = M_PI;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )
#define circC(r) (2 * pi * abs(r))
#define area(a, b, c) ( (gtype) 0.5 * crs((b) - (a), (c) - (a)) )
#define plus(x) ((x) > 0 ? " + " : " - ")

int main() {
	point p[3];
	gtype r;
	cout.precision(2);
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
		r = abs(p[0] - p[1]) * abs(p[1] - p[2]) * abs(p[2] - p[0]) / area(p[0], p[1], p[2]) * 0.25;
		cout << fixed << circC(r) << endl;
	}
	return 0;
}

190 – Circle Through Three Points

by MSiddeek, posted in Algorithms, Geometry, Problems

A geometry problem.
Given three pointsX,Y,Z , find the circle C,r that passes though them. The problem statement illustrates what you have to do:
Given triangle XYZ , the circle centre is the intersection of the perpendicular bisectors on the sides. So, we need to find M1, M2 — the mid points of any two sides — and draw two perpendicular lines which intersect in the centre C . The distance from C to any point X,Y,Z is the radius r .
We need to transform this process into actual computation with vectors. A mid-point is easily determined. A perpendicular to a vector can be found by swapping the coordinates and negating only one of them. Intersection is also a simple task.
\vec{M1} = (\vec{A} + \vec{B}) / 2
\bar{L1} = perp(\vec{AB}) + \vec{M1}
\vec{M2} = (\vec{B} + \vec{C}) / 2
\bar{L2} = perp(\vec{BC}) + \vec{M2}
\vec{C} = intersect(\bar{L1}, \bar{L2})
r = \|\vec{CA}\|
C++ implementation using some geometry tools:

#include <algorithm>
#include <iostream>
#include <complex>
#include <cstdlib>
#include <limits>
using namespace std;

typedef double gtype;
// const
const gtype len_before_point_digits = 1E6;
const gtype epsLen = numeric_limits<gtype>::epsilon() * len_before_point_digits;
// point
typedef complex<gtype> point;
#define x real()
#define y imag()
// vector
#define crs(a, b) ( (conj(a) * (b)).y )
#define perp(p) ( point((p).y, -(p).x) )
// line
#define intrN(a, b, p, q) ( crs((p)-(a),(b)-(a)) * (q) - crs((q)-(a),(b)-(a)) * (p) )
#define intrD(a, b, p, q) ( crs((p)-(a),(b)-(a)) - crs((q)-(a),(b)-(a)) )
// I/O
#define plus(x) ((x) > 0 ? " + " : " - ")

int main() {
	point p[3], v[2][2], c;
	gtype r;
	cout.precision(3);
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> p[2].x >> p[2].y) {
		// perp 1
		v[0][0] = 0.5 * (p[0] + p[1]);
		v[0][1] = perp(p[1] - p[0]) + v[0][0];
		// perp 2
		v[1][0] = 0.5 * (p[1] + p[2]);
		v[1][1] = perp(p[2] - p[1]) + v[1][0];
		// intersect
		c = intrN(v[0][0], v[0][1], v[1][0], v[1][1]) / intrD(v[0][0], v[0][1], v[1][0], v[1][1]);
		r = abs(c - p[0]);
		// out
		gtype h = c.x, k = c.y;
		cout << fixed << "(x" << plus(-h) << abs(h) << ")^2 + (y" <<
				plus(-k) << abs(k) << ")^2 = " << r << "^2" << endl;
		gtype a = 2 * c.x, b = 2 * c.y, d = c.x * c.x + c.y * c.y - r * r;
		cout << fixed << "x^2 + y^2" << plus(-a) << abs(a) << "x" <<
				plus(-b) << abs(b) << "y" << plus(d) << abs(d) << " = 0" << endl;
		cout << endl;
	}
	return 0;
}