Problem 102 says:
Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.
Consider the following two triangles:
A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)
It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.
This problem can be solved in a lot of different ways depending on how one wishes to approach it. You can find the angle of each two point pair of the triangle and the origin and check to see if they add to 360 degrees which would mean the point is inside the triangle, construct a special matrix and take the determinant, etc. However I chose to use a half plane method because it was quicker to implement and didn’t take that much longer to run. Basically we take the two point pairings of the points of the triangle and check to see if the origin is on the same side for all of them. I make the assumption that because they did not mention how points on the edge of the triangle should be handled that there are no such points which allows us to skip some checking.
Solution provided in c#/mono, runs in about .01 second including reading the file.
using System;
using System.Diagnostics;
using System.Drawing;
namespace Problem102
{
class MainClass
{
public static void Main (string[] args)
{
PointF origin = new PointF(0f,0f);
Stopwatch sw = new Stopwatch();
sw.Start();
int TrianglesWithOrigin = 0;
string line;
System.IO.StreamReader file = new System.IO.StreamReader("triangles.txt");
while((line = file.ReadLine()) != null)
{
string[] values = line.Split(',');
PointF p1 = new PointF(float.Parse(values[0]),float.Parse(values[1]));
PointF p2 = new PointF(float.Parse(values[2]),float.Parse(values[3]));
PointF p3 = new PointF(float.Parse(values[4]),float.Parse(values[5]));
if (Inside(origin,p1,p2,p3))
TrianglesWithOrigin += 1;
}
file.Close();
sw.Stop();
Console.WriteLine(TrianglesWithOrigin);
Console.WriteLine(sw.Elapsed);
Console.ReadLine();
}
public static float Sign (PointF p1, PointF p2, PointF p3)
{
return (p1.X - p3.X) * (p2.Y - p3.Y) - (p2.X - p3.X) * (p1.Y - p3.Y);
}
public static bool Inside (PointF pt, PointF p1, PointF p2, PointF p3)
{
bool b1 = Sign(pt, p1, p2) < 0.0f;
bool b2 = Sign(pt, p2, p3) < 0.0f;
bool b3 = Sign(pt, p3, p1) < 0.0f;
return ((b1 == b2) && (b2 == b3));
}
}
}
is an easy to read book that attempts to explain to the reader the differences between research mathematics and the math taught in high schools. It covers subjects such as: mathematical modeling which is the creation of a mathematical system to describe a measurable phenomenon, Abstraction the application of ideas in a general manner, Proofs, Dimensions above an beyond the three we live in, Accurate Estimation plus a whole section on Questions the author (Timothy Gowers) is frequently asked. The book also touches on complex numbers, limits, and infinity making all of these ideas accessible for those that have never seen them before while not focusing on those ideas enough to bore the people already familiar with them (such as those that have taken a college calculus course).