Problem C. Cutpoint on the plane

Author:Г. Гренкин, И. Блинов   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

Doctors of a city polyclinic faced with the problem to find out which combinations of heart rate pi and systolic blood pressure bi can lead to bad feeling. To this end, the doctors measured these parameters for n patients and asked them about their feeling. So, they obtained a sample with two features, that is divided into two classes ci: «1» stands for bad feeling, and «0» denotes feeling well.

The data have been given to the polyclinic information center. Then the problem is to find an optimal separating boundary between classes such that AUC-ROC-metric be as large as possible.

It is required to draw a line through two points from the sample so that when predicting “1” on one side of the line or on the line itself and “0” in other cases, the classification is the best.

AUC is calculated as follows. The number of real ones K1 and real zeros K0 which are located on the positive half-plane are calculated. Then AUC = 0.5 + 0.5 ⋅ K1N1 − 0.5 ⋅ K0N0, where N1 is the total number of ones, N0 is the total number of zeros.

It is worth noting that we call positive (corresponding to the class «1») the half-plane for which AUC is greater.

Input format

The first line contains a single integer n. This is followed by n triples of the numbers pi, bi, ci. The numbers pi, bi are real, ci are 0 or 1. It is guaranteed that there is at least one point belonging to class 1 and at least one point belonging to class 0. There are no three points (pi, bi) at same line.

Output format

Output a single real number — maximal value of AUC metric with at least 3 digits after decimal point.

Constraints

2 ≤ n ≤ 1000 0 ≤ pi, bi ≤ 109 ci ∈ 0, 1

Sample tests

No. Standard input Standard output
1
4
0.0 0.0 1
1.0 1.0 1
0.0 1.0 0
1.0 0.0 0
0.75
2
5
1 1 1
0 1 1
1 0 1
0 0 1
3 2 0
1

0.084s 0.022s 15