Hôm nay trên đường đi học, Naot vô tình nhặt được trên đường một mảnh giấy chứa ~2~ mảng số nguyên ~a~ và ~b~ có độ dài ~n~. Phía sau mặt giấy có ghi một câu đố với nội dung như sau:
Gọi số nguyên thứ ~i~ ~(0 \le i < n)~ (của mảng ~a~ và mảng ~b~ là ~a_i~ và ~b_i~. Cho hàm ~f~ được định nghĩa như sau:
float f(float x, int a[], int b[], int n) {
float res = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i != j) {
int da = a[i] - a[j];
int db = b[i] - b[j];
res = max(res, da * cos(x) + db * sin(x));
}
}
}
return res;
}
Hãy tìm giá trị nhỏ nhất của hàm ~f~ với ~2~ mảng số được cho trước. Kết quả được chấp nhận với sai số ~10^{-6}~.
Input
Dòng đầu tiên chứa số nguyên dương ~n~ (~2 \leq n \leq 10^6~).
Dòng tiếp theo chứa ~n~ số nguyên ~a_0, a_1, ..., a_{n - 1}~ (~|a_i| \leq 10^5~).
Dòng tiếp theo chứa ~n~ số nguyên ~b_0, b_1, ..., b_{n - 1}~ (~|b_i| \leq 10^5~).
Output
- Xuất ra giá trị nhỏ nhất mà hàm ~f~ có thể đạt được.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~20~ | ~n \le 10~ |
2 | ~30~ | ~n \le 1000~ |
3 | ~50~ | ~n \le 10^6~ |
Sample Input 1
5
3 2 9 3 2
5 5 5 5 5
Sample Output 1
0.0000000000
Sample Input 2
4
1 0 1 2
0 -1 -2 -1
Sample Output 2
1.4142135624
Sample Input 3
5
3 1 5 3 4
7 2 9 3 5
Sample Output 3
1.6712580436
Notes
Ở trong ví dụ thứ nhất, giá trị ~x~ để hàm ~f~ đạt giá trị nhỏ nhất là ~x = \frac{\pi}{2}~.
Ở trong ví dụ thứ hai, giá trị ~x~ để hàm ~f~ đạt giá trị nhỏ nhất là ~x = \frac{\pi}{4}~.
Comments