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]).