Лучший первый вопрос

Решающее дерево начинается с одного вопроса «x ≤ t?». Есть n примеров: у каждого числовой признак x_i и ответ y_i — 0 или 1. Вопрос делит примеры на две непустые группы, и хороший вопрос — тот, после которого неопределённость меньше всего. Найдите порог t с наибольшим приростом информации

$$\mathrm{IG} = H(\text{все}) - \frac{n_{\le}}{n}\,H(\text{группа } x \le t) - \frac{n_{>}}{n}\,H(\text{группа } x > t),$$

где H — энтропия группы в битах: если в группе доля единиц p, то H = −p log₂ p − (1 − p) log₂ (1 − p) (слагаемое с нулевой долей считается нулём).

Два теста — землетрясения магнитудой от 5 за 2015–2021 годы из каталога USGS: признак — магнитуда (в сотых) или расстояние до ближайшего города от 10 тысяч жителей (км), ответ — сообщил ли кто-нибудь, что почувствовал толчок.

Вход

В первой строке n (2 ≤ n ≤ 200 000). В каждой из следующих n строк — целые x_i (|x_i| ≤ 10⁹) и y_i ∈ {0, 1}.

Выход

Если все x_i одинаковы, выведите -: ни один вопрос не делит примеры. Иначе выведите два числа: порог t и прирост информации. Подходит любой порог, при котором обе группы непустые и прирост отличается от наибольшего возможного не больше чем на 10⁻⁹; прирост проверяется с погрешностью 10⁻⁶.

8
1 0
2 0
3 0
4 1
5 0
6 1
7 1
8 1

3.5 0.548794941

3
42 1
42 0
42 1

-