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