Page not loading? Try clicking here.
Placeholder

#8443
Subtask

공주 파티 2s 256MB

Problems

N 명의 공주들이 수직선 위에 있다.

공주들은 수직선 위의 한 곳에 모여 파티를 하려고 한다.

위치 x 에 있는 공주가 위치 k 의 파티장으로 이동하는 데에는 | x - k| 의 시간이 걸린다.

그런데, 공주들은 예쁜 모습으로 파티장에 가야 하므로, 출발하기 전에 집에서 시간을 들여 화장을 해야 한다.

공주들마다 화장하는 시간이 각각 다르고, 이는 정수 t_i~~ ( 1 ≤ i ≤ N ) 로 주어진다.

즉, i 번째 공주의 위치를 x_i 라고 하면,

이 공주는 위치 k 의 파티장에 t_i + | x_i - k | 시간 후에 도착한다.

즉, 모든 공주는 시간 0 에 화장을 하기 시작하고, 화장이 끝나는 즉시 파티장으로 출발한다.

모든 공주가 파티장에 도착하면, 그 즉시 파티는 시작된다.

당신은 파티가 가장 빨리 시작하기를 원한다.

각 공주 별로 x_i,~~ t_i 가 주어졌을 때, 가장 빠르게 파티가 시작하기 위한 파티장의 위치를 구하자.


Input

첫 줄에는 N 이 입력된다. ( 1 ≤ N ≤ 200,000 )

두 번째 줄에는 공주들의 위치인 정수 x_i 가 입력된다. ( 0 ≤ x_i ≤ 108 )

세 번째 줄에는 공주들의 화장 소요 시간 정수 t_i 가 입력된다. ( 0 ≤ t_i ≤ 108 )

x 좌표가 같은 공주들이 있을 수 있다.


Output

파티장의 위치를 소수 둘째 자리에서 반올림하여 소수 첫째 자리까지 출력한다.

소수 첫째 자리가 0 일지라도 출력되어야 한다.


Subtask

# Score Condition
#115

t_i = 0

#215

1 ≤ N ≤ 100, 0 ≤ x_i ≤ 1,000

#330

t > 0 인 공주는 정확히 한 명이다.

#440

제약 조건 없음


Example #1

5
6 3 2 1 8
0 0 0 0 0
4.5

파티를 x = 4.5 에서 개최하면,

각 공주는 [ 1.5, 1.5, 2.5, 3.5, 3.5 ] 시간 만에 파티장에 도착한다.

따라서 3.5 시간 후에 파티가 시작되며,

이 방법이 가장 빠르다.


Example #2

3
3 1 2
2 4 1
1.0

파티를 x = 1.0 에서 개최하면,

첫 번째 공주는 2 + | 3 - 1 | = 4 시간만에 도착

두 번째 공주는 4 + | 1 - 1 | = 4 시간만에 도착

세 번째 공주는 1 + | 2 - 1 | = 2 시간만에 도착

따라서 4시간 만에 파티를 시작할 수 있고, 이 방법이 가장 빠르다.



Source

Codeforces Round 823
You must sign in to write code.