You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

决策树生成算法递归地产生决策树，直到不能继续下去为止，在这个过程中，最关键的是确定每个节点的阈值。一种传统方法是划分之后，需要使得数据集的熵减最大化。

而小明同学面对的问题是一个基座问题：只有一个特征的数据集的二分类问题。如果构建出二叉树，那么将形如：”一个根节点配两个儿子节点“的结构。

在这种问题下，小明希望通过一个更加简洁的策略来获得结果：枚举阈值，得到验证集上的最优的准确率。请问给定验证集，需要设定怎样的阈值使得准确率最大化。

请输出小$A$通过他提出的寻找阈值的策略，在验证集上可以达到的最优 准确率

输入描述

第一行一个整数$M(1<=M<=10^5)$ 表示验证集条数

随后 $M$ 行为验证集特征和 $label$，每行 $2$ 个整数，第一个数为该条数据的特征，最后一个整数为该条数据的 $label \in [0,1]$ 。

随后一行两个整数$L,R$ 分别代表左子树和右子数的$label$ , $L\neq R且L,R\in[0,1]$

输出描述

第一行，一个浮点数，为验证集可达到的最优准确率，四舍五入保留小数点后 $3$ 位。

样例1

输入

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

输出

0.800

说明

设定阈值$=5$ , 那么所有样本进入左子树，被归类为0 ， 准确率为$\frac{4}{5}=0.8$ , 注意保留三位小数

样例2

输入

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

输出

1.000

说明

设定阈值$=3$ , 那么样本$1,2,3$进入左子树，被归类为1 ， 样本$4,5,6$ 进入右子树，被归类为$0$ ， 全部分类正确，准确率为$1$

提示

$本题准确率的计算方法为:\frac{预测正确的样本个数}{总样本个数}$