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

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

Кольцевые дороги

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

요약
내부 원 위 각도 a의 점에서 외부 원 위 각도 b의 점까지, 두 원을 따라 자유롭게 이동하고 바깥쪽으로만 향하는 연결 도로를 이용할 때의 최단 거리를 구한다.
난이도

보통10점 중 6점

유형
기하, 정렬, 이분 탐색, 누적 합
정답자
아직 제출이 없습니다

문제

Дорожная сеть Нью-Йорка состоит из двух кольцевых дорог, являющихся концентрическими окружностями, и нескольких дорог, соединяющих их. Введем систему координат так, что центр окружностей совпадает с началом координат, а ось OY направлена на север. Первая кольцевая дорога имеет радиус 10 километров, а вторая --- 20. По кольцевым дорогам можно двигаться в любую сторону. Дороги, соединяющие их, являются односторонними, и по ним можно проехать только от внутреннего кольца до внешнего. Всего дорог, соединяющих кольца, nn штук, они задаются углами ang_iang\_i, ii-й дорогой является заключенный между окружностями отрезок луча, имеющего угол наклона ang_iang\_i от оси OX.

Сейчас Ньют продумывает план поимки Нюхля. Помогите ему, ответьте на qq его вопросов. Вопрос номер jj задается двумя числами: a_ja\_j и b_jb\_j, он значит, что Ньют хочет узнать кратчайшее расстояние от точки на первом кольце, такой, что угол наклона отрезка, проведенного в нее из начала координат, равен a_ja\_j, до точки на втором кольце, имеющей аналогичный угол наклона равный b_jb\_j.

입력

В первой строке даны два числа nn и qq --- количество дорог, соединяющих кольцевые дороги, и количество вопросов Ньюта, соответственно (1≤n,q≤1051 \le n, q \le 10^5).

В следующих nn строках дано по одному вещественному числу ang_iang\_i --- угол наклона луча, соответствующего ii-й дороге, в градусах (0≤ang_i<3600 \le ang\_i < 360).

В следующих qq строках дано по два вещественных числа a_ja\_j и b_jb\_j --- jj-й вопрос Ньюта (0≤a_j,b_j<3600 \le a\_j, b\_j < 360).

Все углы даны в градусах. Все вещественные числа даны с не более чем 6 цифрами после запятой.

출력

На каждый вопрос выведите в новой строке одно вещественное число --- кратчайшее расстояние между данными точками, абсолютная или относительная погрешность не должна превышать 10−610^{-6}.

힌트

Пояснение к тесту из примера. Кратчайший путь для первого и второго вопроса соответственно.

예제1

  1. 예제 1

    입력
    1 2
    180
    0 0
    60 300
    
    예상 출력
    104.2477796077
    72.8318530718