Стена

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

요약
한쪽 진영의 점 n개와 다른 진영의 점 m개가 주어질 때 두 집합을 분리하는 원을 찾을 수 있는지 판정하고, 가능하면 중심과 반지름을 출력한다.
난이도

어려움10점 중 8점

유형
기하, 분할 정복, 그리디
정답자
아직 제출이 없습니다

문제

После завоевания Эджландии правительства Флатландии и союзников решили разделить ее столицу на зоны влияния. После длительных переговоров решено было построить стену для отделения территории Флатландии от территории союзников. Из-за стремления лидеров завоевателей к совершенству, решено было построить стену в форме окружности.

Каждый из завоевателей отметил несколько точек на карте, которые он был хотел иметь в своей зоне влияния. Стену следует построить таким образом, чтобы точки, выбранные Флатландией, оказались с одной стороны от стены, а точки, выбранные союзниками --- с другой. Стена будет достаточно тонкой и может пройти с любой стороны от точки, лежащей непосредственно через нее.

Помогите завоевателям построить стену.

입력

Первая строка входного файла содержит nn и mm --- количество точек, которые интересуют Флатландию и союзников, соответственно (2≤n,m≤1202 \le n, m \le 120). Следующие nn строк содержат по два целых числа: координаты точек, отмеченных Флатландией. Затем следует mm строк, которые описывают точки союзников. Координаты не превышают 10410^4 по модулю, все точки различны.

출력

Если можно построить стену, выведите <<YES>> на первой строке входного файла. На второй строке выведите три вещественных числа: координаты центра и радиус окружности стены. Ответ должен быть выведен с точностью не менее 10−610^{-6}, но рекомендуется выводить как можно больше знаков после десятичной точки.

Если построить стену нельзя, выведите <<NO>> на первой строке выходного файла.

예제3

  1. 예제 1

    입력
    2 2
    0 0
    0 1
    1 0
    1 1
    
    예상 출력
    YES
    0 0.5 0.5
    
  2. 예제 2

    입력
    2 2
    0 0
    1 1
    1 0
    0 1
    
    예상 출력
    YES
    0.5 0.5 0.70710678118654752
    
  3. 예제 3

    입력
    4 2
    0 0
    2 2
    2 0
    0 2
    1 1
    5 5
    
    예상 출력
    NO