Задача C. Cutpoint on the plane ≡

Условие

В городской поликлинике поставили задачу выяснить, какие сочетания пульса p_i и артериального давления b_i приводят к плохому самочувствию. С этой целью врачи измерили эти параметры у n пациентов, спросив у них о самочувствии. Получилась выборка с двумя признаками, разделенная на два класса c_i: «1» - плохое самочувствие, «0» - нормальное самочувствие.

Данные передали в информационный центр поликлиники, где хотят построить оптимальную разделяющую границу между классами так, чтобы AUC-ROC-метрика оказалась наибольшей.

Требуется провести прямую через две точки из выборки так, чтобы при предсказании «1» по одну сторону от прямой или на самой прямой и «0» в остальных случаях классификация получилась наилучшей.

AUC вычисляется следующим образом. Вычисляется число реальных единиц K₁ и число реальных нулей K₀, расположенных в положительной полуплоскости. Тогда AUC = 0.5 + 0.5 ⋅ K₁N₁ − 0.5 ⋅ K₀N₀, где N₁ – общее число единиц, N₀ – общее число нулей.

Отметим, что положительной (соответствующей классу «1») считаем ту полуплоскость, в которой AUC больше.

Формат входных данных

Первая строка содержит одно целое число n. Далее следует n троек чисел p_i, b_i, c_i. Числа p_i, b_i вещественные, c_i — это 0 или 1. Гарантируется, что существует хотя бы одна точка относящаяся к классу 1 и хотя бы одна точка относящаяся к классу 0. Никакие три точки (p_i, b_i) не лежат на одной прямой.

Формат выходных данных

Выведите одно вещественное число — максимальное значение метрики AUC с точностью до 3х знаков после запятой.

Ограничения

2 ≤ n ≤ 1000 0 ≤ p_i, b_i ≤ 10⁹ c_i ∈ 0, 1

Примеры тестов

4
0.0 0.0 1
1.0 1.0 1
0.0 1.0 0
1.0 0.0 0

0.75

5
1 1 1
0 1 1
1 0 1
0 0 1
3 2 0

1