ACMP 658

Ссылка на задачу

• ACMP #658 — Фермерское счастье

Комментарии

См. задачу Codeforces #13.D и её обсуждение (1, 2, 3).

Считываем точки в массив p[], сортируем по координате x. Считаем значения d[i][j] — сколько точек лежат ниже полуинтервала [p[i]; p[j]).

Критерий отсутствия точек в треугольнике (p[i], p[j], p[k]), где i < j < k, — равенство значений d[i][k] - X и d[i][j] + d[j][k] - Y, где X = 1, если p[j] лежит ниже [p[i]; p[k]), и Y = 1, если p[i] лежит ниже [p[j]; p[k]).