UVa 438

From Algorithmist
Jump to navigation Jump to search

438 - The Circumference of the Circle[edit]

Summary[edit]

Given three non-collinear points in the plane, calculate the circumference of the circle that intersects them.

Explanation[edit]

There is always a circle that intersects any 3 points in the plane. Since the ones given here are noncollinear, i.e. there is no straight line that can cross them all, that means that if you join the points with lines a triangle is formed. Using this triangle you can find the centre of the circle, and with it, the radius. Once you have the radius you have the circumference. In order to find this central point find the midpoint on each line, then draw a perpendicular line for each one and the point in which they intersect will be the center of the circle. At least 2 of the original points will lie on the circumference, so there you have the radius.

Implementations[edit]

Use double for the variables or you might get WA due to inexact results.

Optimizations[edit]

Instead of going through the process of finding midpoints, slopes and doing algebra, you can follow the reference below and search the single formula for calculating the radius of a circle given 3 points that intersect it.

Input[edit]

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[edit]

3.14
4.44
6.28
31.42
62.83
632.24
3141592.65

Solutions[edit]

References[edit]

http://www.wikihow.com/Calculate-the-Radius-of-a-Circle