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

Условие

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

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

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

AUC вычисляется следующим образом. Вычисляется число реальных единиц $K_1$ и число реальных нулей $K_0$, расположенных в положительной полуплоскости. Тогда $AUC = 0.5 + \frac{0.5 \cdot K_1}{N_1} - \frac{0.5 \cdot K_0}{N_0}$, где $N_1$ – общее число единиц, $N_0$ – общее число нулей.

Отметим, что положительной (соответствующей классу «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 \le n \le 1000$ $0 \le p_i,\,b_i \le 10^9$ $c_i \in {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