 The file attached with this problem contains a list having $100$ lines. Eight numbers $x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$ are written in each line, which correspond to a quadrilateral whose vertices have coordinates $A_1=(x_1, y_1),\ A_2=(x_2, y_2),\ A_3=(x_3, y_3),\ A_4=(x_4, y_4)$ (in Cartesian plane). There are $N$ quadrilaterals in this list which are concave.

Find $N+6.$

Details and Assumptions:

• As an explicit example, suppose the list had $2$ lines, and the following numbers were written on those two lines: $\begin{array}{lrrrrrrrrl} &1, &1, &2, &2, &3, &3, &4, &4 \\ &1, &-1, &2, &-2, &3, &-3, &4, &-4 &.\end{array}$ We have two quadrilaterals, the first one having its vertices at points $(1, 1), (2, 2), (3, 3), (4, 4),$ and the second one having its vertices at points $(1, -1), (2, -2), (3, -3), (4, -4).$ Your job is to find out how many of them are concave.

• Link to the file: http://pastebin.ca/2679837.

• If one of the vertices lies on the line joining two other vertices, consider the resulting figure as convex.

• This is a computer science problem, and is inspired from ProjectEuler (I don't remember the problem number at the moment).

×