207. Обобщённый AUC

Классический ROC-AUC равен

где $t_i, t_j$ — правильные ответы (бинарные) для объектов $i$ и $j$, $N_0, N_1$ - количества 0 и 1 среди правильных ответов соответственно, а $y_i, y_j$ — предсказания модели для объектов $i$ и $j$. Рассмотрим обобщённый AUC, который определён не только для бинарных ответов:

Даны массив правильных ответов и массив предсказаний модели.

Необходимо посчитать обобщённый AUC.

В первой строке указано одно число $N$ — число объектов в выборке ($2 \leqslant N \leqslant 100000$).

В каждой из следующих $N$ строк через пробел указаны два вещественных числа $t_i$ и $y_i$ ($0 \le t_i, y_i \le 10)$ (с точностью не более 6 цифр после десятичной точки): правильный ответ примера и предсказание модели для этого примера.

Гарантируется, что существуют два таких номера $i$ и $j$, что $t_i \ne t_j$.

Выведите одно число (значение обобщённого AUC) с точностью как минимум 6 значащих цифр после десятичной точки.

Гарантируется, что все закрытые тесты соответствуют одному из трех наборов ограничений:

1)

• $n \le 10$;
• $0 \le t_i, y_i \le 10$;
• $t_i, y_i$ целые числа;

2)

• $n = 1000$;
• $0 \le t_i, y_i \le 10$;
• $t_i, y_i$ целые числа;

3)

• $n = 10^5$;
• $0 \le t_i, y_i \le 1$;
• $t_i, y_i$: вещественные числа, не более 6 знаков после запятой.
• гарантируется, что все $t_i$, $y_i$ сгенерированы случайно с равномерным распределением в отрезке $[0; 1]$.