Будем решать задачу для каждой точки P отдельно и решим ее за О(N). Видимо, самый простой способ - посчитать количество треугольников, не содержащих P, а затем вычесть это количество из общего количества треугольников.

Рассмотрим тройки вершин A, B, C, образующих треугольник, таких что P не лежит в ABC, кроме того, AB разделяет P и C и P лежит в многоугольнике справа от АB по часовой стрелке. Заметим, что для каждого треугольника его вершины в некотором порядке образуют такую тройку и каждая тройка дает нам треугольник. То есть можно вместо треугольников без P считать такие тройки.

Рассмотрим произвольную вершину многоугольника, мы хотим, чтобы она стала вершиной А в тройке. Тогда множество вершин, подходящих на место B в тройке мы получим идя диагоналями от A по часовой стрелке, пока не дойдем до P. Причем для каждой подходящей вершины B количество треугольников - это расстояние между A и B (в вершинах) по часовой стрелке минус один. То есть для фиксированной А мы получаем сумму арифметической прогрессии по подходящим B.

Единственное, что осталось понять - как найти последнюю B для А. Ну а эта задача просто решается двумя указателями сразу для всевозможных А.