아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Traveling Monk

면접 대비

시간 제한2초메모리 제한1024 MB

요약
스님의 오르막과 내리막 고도 변화가 구간별로 주어질 때, 두 여정이 같은 고도에 있는 가장 이른 시각을 구한다.
난이도

보통10점 중 4점

유형
투 포인터, 시뮬레이션, 구현
정답자
아직 제출이 없습니다

문제

The following puzzle was popularized by Martin Gardner's book "My Best Mathematical and Logic Puzzles," although it appears first in the monograph "On Problem-Solving" by the Gestalt psychologist Karl Dunker.

One morning, exactly at sunrise, a Buddhist monk began to climb a tall mountain. The narrow path, no more than a foot or two wide, spiraled around the mountain to a glittering temple at the summit.

The monk ascended the path at varying rates of speed, stopping many times along the way to rest and eat the dried fruit he carried with him. He reached the temple shortly before sunset. After several days of fasting and meditation he began his journey back along the same path, starting at sunrise and again walking at variable speeds with many pauses along the way.  His average speed descending was, of course, greater than his average climbing speed.

Prove that there is a spot along the path that the monk will occupy on both trips at precisely the same time of day!

You can probably see why this is true - but can you write a program that computes the time at which the monk will be at the same spot during his ascent and descent?

입력

The input consists of a single test case. The first line contains two integers aa (0<a≤5,0000 < a \le 5\\,000) and dd (0<d≤5,0000 < d \le 5\\,000) denoting the number of segments during the ascent and descent, respectively. This is followed by aa lines, each containing two integers hh (0≤h≤1,0000 \le h \le 1\\,000) and tt (0<t≤1000 < t \le 100) denoting the positive change in elevation (hh) the monk gained during this segment and the time it took (tt).  If the monk rests and eats during a segment, hh will be 00.

This is followed by dd lines, each containing two integers hh (0≤h≤1,0000 \le h \le 1\\,000) and tt (0<t≤1000 < t \le 100) denoting the change in elevation (hh) the monk descended during this segment and the time it took (tt).  If the monk rests and eats during a segment, hh will be 00.

출력

Output a single floating point number, the earliest point in time at which the monk occupies the same spot during his climb and his descent.  The monk starts his ascent and his descent at time 00 on both days.

Your answer will be considered correct if its absolute or relative error does not exceed 10−510^{-5}.

예제3

  1. 예제 1

    입력
    1 1
    10 11
    10 10
    
    예상 출력
    5.238095
    
  2. 예제 2

    입력
    3 1
    4 2
    0 3
    6 3
    10 7
    
    예상 출력
    4.200000
    
  3. 예제 3

    입력
    3 3
    2 3
    0 5
    3 1
    3 4
    0 2
    2 2
    
    예상 출력
    4.000000