Bedao Grand Contest 16 - Giấy vụn trên đường

View as PDF

Submit solution


Points: 1.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.


There are no comments at the moment.