题号：NC223861
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld
题目描述
As a student of the Scholomance Academy, you are studying a course called \textit{Machine Learning}. You are currently working on your course project: training a binary classifier.
A binary classifier is an algorithm that predicts the classes of instances, which may be positive)
or negative )
. A typical binary classifier consists of a scoring function 
that gives a score for every instance and a threshold 
that determines the category. Specifically, if the score of an instance %20%5Cgeq%20%5Ctheta)
, then the instance 
is classified as positive; otherwise, it is classified as negative. Clearly, choosing different thresholds may yield different classifiers.
Given the actual classes and predicted scores of the instances in a dataset, can you compute the
of your classifier?
A binary classifier is an algorithm that predicts the classes of instances, which may be positive
Of course, a binary classifier may have misclassification: it could either classify a positive instance as negative (false negative) or classify a negative instance as positive (false positive).
Given a dataset and a classifier, we may define the true positive rate (
) and the false positive rate (
) as follows:
where 
is the number of true positives in the dataset; 
are defined likewise.
Now you have trained a scoring function, and you want to evaluate the performance of your classifier. The classifier may exhibit different TPR and FPR if we change the threshold. Let %2C%20FPR(%5Ctheta))
be the 
when the threshold is , define the 
() as
%7CFPR(%5Ctheta)%20%5Cleq%20r%5C%7D%20d%20r)
where the integrand, called
(ROC), means the maximum possible of given that 
.
Now you have trained a scoring function, and you want to evaluate the performance of your classifier. The classifier may exhibit different TPR and FPR if we change the threshold
where the integrand, called
Given the actual classes and predicted scores of the instances in a dataset, can you compute the
For example, consider the third test data. If we set threshold 
, there are 3 true positives, 2 false positives, 2 true negatives, and 1 false negative; hence, %20%3D%200.75)
and %20%3D%200.5)
. Also, as varies, we may plot the ROC curve and compute the AUC accordingly, as shown in Figure 1.
输入描述:
The first line contains a single integer
, the number of instances in the dataset. Then follow
and an integer
, denoting the actual class and the predicted score of an instance.
It is guaranteed that there is at least one instance of either class.
输出描述:
Print the.
