A farmer fences off triangular pens in a field and wants to know, for each sheep's GPS position, which pen it's standing in.
Write pen_of(pens, sheep) -> list[int]:
pensis a list of triangles, each a tuple of three corners((x1, y1), (x2, y2), (x3, y3))with integer coordinates. Corners may be listed clockwise or counter-clockwise, and every triangle has non-zero area. Pens may overlap.sheepis a list of integer points(x, y).- Return one integer per sheep: the smallest index of a pen that contains it, or
-1if it's in none. A sheep standing exactly on a fence (an edge or a corner) counts as inside.
pens = [((0, 0), (4, 0), (0, 4)), # pen 0
((10, 0), (4, 3), (10, 6))] # pen 1, listed clockwise
pen_of(pens, [(1, 1), (2, 2), (8, 3), (4, 3), (5, 5)])
# [0, 0, 1, 1, -1]
# (2, 2) is on pen 0's slanted fence; (4, 3) is a corner of pen 1
Constraints: up to 200 pens and 200 sheep, coordinates between -10^9 and 10^9. Use integer arithmetic only: no floats, no division, no angles.
Show hint
The sign of cross(a, b, c) = (b.x - a.x)·(c.y - a.y) - (b.y - a.y)·(c.x - a.x) tells you which side of the line a→b the point c is on (0 when collinear). A point is in a triangle (boundary included) exactly when it is not strictly left of one edge and strictly right of another, whichever way the corners are listed.