A Geometry Problem

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 162M

Problem type

You are given a polyline (x_1, y_1) through (x_N, y_N). Compute the minimum length of a vertical segment (parallel to the y-axis) with its bottom endpoint somewhere on the polyline such that from every point on the polyline, the segment is at least partially visible.

Constraints

1 \le N \le 300

|x_i|, |y_i| \le 10^6

Input Specification

The first line contains a single integer, N.

The next line contains N space-separated integers, the ith being x_i. These will be presented in increasing order

The next line contains N space-separated integers, the ith being y_i.

Output Specification

Output the desired length to exactly three decimal places.

Sample Input

6
1 2 4 5 6 7
1 2 2 4 2 1

Sample Output

1.000

Comments

There are no comments at the moment.