Bài tập | NEU OJ

Cho mẫu số liệu gồm $n$ số nguyên. Sử dụng phương pháp loại trừ trung vị để tính tứ phân vị như sau:

Sắp xếp dãy số tăng dần.
Tính trung vị của dãy để xác định điểm chia: nếu $n$ chẵn, nửa dưới là $\lfloor n/2 \rfloor$ phần tử đầu, nửa trên là $\lfloor n/2 \rfloor$ phần tử cuối; nếu $n$ lẻ, loại bỏ phần tử chính giữa (trung vị), nửa dưới và nửa trên là các phần tử còn lại ở hai bên.
$Q_1$ = trung vị của nửa dưới; $Q_3$ = trung vị của nửa trên (trung vị của $m$ số: nếu $m$ lẻ lấy số ở giữa, nếu $m$ chẵn lấy trung bình cộng hai số ở giữa).
$IQR = Q_3 - Q_1$ .
Một giá trị $x$ được coi là ngoại lai nếu $x < Q_1 - 1.5 \cdot IQR$ hoặc $x > Q_3 + 1.5 \cdot IQR$ .

Ví dụ: Dãy $1,2,2,3,4,5,6,7,8,100$ ( $n=10$ chẵn): nửa dưới $=1,2,2,3,4$ có trung vị $Q_1=2$ ; nửa trên $=5,6,7,8,100$ có trung vị $Q_3=7$ . $IQR=5$ , ngưỡng trên $=7+7.5=14.5$ nên $100$ là ngoại lai.

Định dạng đầu vào:
Dòng 1: số nguyên $n$ ( $2 \le n \le 10^5$ ). Dòng 2: $n$ số nguyên $x_1, \ldots, x_n$ ( $-10^6 \le x_i \le 10^6$ ), cách nhau bởi dấu cách.
Định dạng đầu ra:
In ra 4 dòng: Dòng 1: giá trị $Q_1$ , định dạng %.2f. Dòng 2: giá trị $Q_3$ , định dạng %.2f. Dòng 3: giá trị $IQR$ , định dạng %.2f. Dòng 4: danh sách các giá trị ngoại lai (giá trị gốc trong dãy, có thể lặp lại nếu xuất hiện nhiều lần), sắp xếp tăng dần, mỗi số định dạng %.2f, cách nhau bởi dấu cách; nếu không có ngoại lai nào, in ra Khong co.

Ví dụ với input trên, output là:
```
2.00
7.00
5.00
100.00
```

solution

Đề bài: [Xác suất - Thống kê] Tứ phân vị và phát hiện ngoại lai theo quy tắc Tukey