Punkt indeholdt i trekant

Problem nummer 102 på ProjectEuler.net går ud på at finde ud af om en række trekanter indeholder deres origin (punktet (0,0) i et koordinat system).

Da jeg først fandt ud af hvordan man beregner arealet af en trekant, når man kun kender punkterne for de tre hjørner, var opgaven faktisk ikke så kompliceret.

Beregn areal af trekant ud fra koordinater

Formlen for hvordan man beregner arealet af en trekant ud fra dens tre koordinater A, B, C:

Generer nye trekanter

Herefter genereres tre ny trekanter ud fra punkterne i trekanten ABC og punktet P

Vi kalder trekanterne for ABP, ACP og CBP

Nu beregnes de nye trekanters arealer og hvis deres samlede areal er lig med arealet af ABC, så er punktet indeholdt i trekanten.

Eksempel

Trekanten T har punkterne A(-340,495), B(-153,-910) og C(835,-947). Vi skal afgøre om punktet p(0,0) er indeholdt i trekant T?

    Arealet af den oprindelige trekant ABC er:
        A = (-340 * (-910 --947) + (-153) * (-947 - 495) + 835 * (495 --910)) / 2
          = (-340 * 37 + (-153) * (-1442) + 835 * 1405) / 2
          = (-12580 + 220626 + 1173175) / 2
          = 1381221 / 2
          =  690610.5 

    Arealet af trekant ABP er:
        A = (-340 * (-910 - 0) + -153 * (0 - 495) + 0 * (495 --910)) / 2
          = ...
          =  192567.5 

    Arealet af trekant ACP er:
        A = (-340 * (0 --947) + 0 * (-947 - 495) + 835 * (495 - 0)) / 2
          = ...
          =  45672.5 

    Arealet af trekant CBP er:
        A = 0 * (-910 --947) + -153 * (-947 - 0) + 835 * (0 --910) / 2
          = ...
          =  452370.5 

    Arealet af de tre trekanter ABP, ACP, CBP er:
        192567.5 + 45672.5 + 452370.5 =  690610.5 

    Det ses at arealet af de tre trekanter er lig med den originale trekant ABC's areal.
    Vi kan derfor konkludere at punktet p(0,0) er indeholdt i trekant ABC.