## Wednesday, May 21, 2008

### Project Euler p102 - finding origin

Problem description:
-----------------------------------------------------
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.

Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.
-----------------------------------------------------

I`ve exploited the idea that for origin to be in the triangle interior, triangle lines segments should cross x and y axis 2 times: x+ / x- and y+ / y-.
Basically it is enough to check does triangle cross y+ and y- axis parts, but I didn`t know that and checked both axis. This worked too :-)

Solution ( C# as always):

`using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.IO;namespace ConsoleApplication1{    class Program    {        static int[][] ReadTriangleCoordinates(string file)        {            int[][] res;            StreamReader sr = new StreamReader(file);            res = Array.ConvertAll(sr.ReadToEnd().TrimEnd().Split("\n".ToCharArray()),                   s => {return Array.ConvertAll(s.Split(",".ToCharArray()),                                         n => { return int.Parse(n); }) ;});            sr.Close();            return res;        }        static void CrossesAxisAt(int x1,                                   int y1,                                   int x2,                                   int y2,                                   out double? xAt,                                   out double? yAt)        {            int dx = x2 - x1;            int dy = y2 - y1;            int xmin = Math.Min(x1, x2);            int ymin = Math.Min(y1, y2);            int xmax = Math.Max(x1, x2);            int ymax = Math.Max(y1, y2);            double? xcross;            double? ycross;            double a;            double b;            if (dx == 0)            {                xcross = x1;                ycross = null;            }            else if (dy == 0)            {                xcross = null;                ycross = y1;            }            else            {                a = (double)dy / (double)dx;                b = y1 - (a * x1);                xcross = -(b / a);                ycross = b;            }            if (xcross != null)            {                if (xcross < xmin || xcross > xmax                                   || ymin > 0 || ymax < 0)                    xcross = null;            }            if (ycross != null)            {                if (ycross < ymin || ycross > ymax                                   || xmin > 0 || xmax < 0)                    ycross = null;            }            xAt = xcross;            yAt = ycross;        }        static bool ContainsOrigin(int[] abc)        {            double? xc1, xc2, xc3;            double? yc1, yc2, yc3;            int xposc = 0, xnegc = 0, yposc = 0, ynegc = 0;            bool res;            CrossesAxisAt(abc, abc, abc, abc, out xc1, out yc1);            CrossesAxisAt(abc, abc, abc, abc, out xc2, out yc2);            CrossesAxisAt(abc, abc, abc, abc, out xc3, out yc3);            xposc = ((xc1 > 0) ? 1 : 0) + ((xc2 > 0) ? 1 : 0) + ((xc3 > 0) ? 1 : 0);            xnegc = ((xc1 < 0) ? 1 : 0) + ((xc2 < 0) ? 1 : 0) + ((xc3 < 0) ? 1 : 0);            yposc = ((yc1 > 0) ? 1 : 0) + ((yc2 > 0) ? 1 : 0) + ((yc3 > 0) ? 1 : 0);            ynegc = ((yc1 < 0) ? 1 : 0) + ((yc2 < 0) ? 1 : 0) + ((yc3 < 0) ? 1 : 0);            if (xposc > 0 && xnegc > 0 && yposc > 0 && ynegc > 0)                res = true;            else                res = false;            return res;        }        static int TrianglesWithOrigin(string file)        {            int[][] tr = ReadTriangleCoordinates(file);            int trcount = 0;            for (int i = 0; i < tr.Length; i++)            {                if (ContainsOrigin(tr[i]))                    trcount++;            }            return trcount;        }        static void Main(string[] args)        {            Console.WriteLine(TrianglesWithOrigin("C:\\ProjectEuler\\triangles.txt"));            Console.ReadLine();        }    }}`