ЕЖЕГОДНАЯ ОЛИМПИАДА ПО ПРОГРАМИРОВАНИЮ В ЛИЧНОМ ЗАЧЁТЕ

11 мая регистрация участников на сайте http:\olimp.bstu.by
Дата проведения 17 мая
Время проведения с 9:00 до 12:00

 
HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > VIII ОЛИМПИАДА БрГТУ ПО ПРОГРАММИРОВАНИЮ ДЛЯ ШКОЛЬНИКОВ - очный тур > problem:


E. Сладкоежка

VIII ОЛИМПИАДА БрГТУ ПО ПРОГРАММИРОВАНИЮ ДЛЯ ШКОЛЬНИКОВ - очный тур

Start: Feb.26.2022 at 10:30:00 AM
Finish: Feb.26.2022 at 01:30:00 PM
The contest is finished!
• Contest scoreboard

Contest problems

• A. Подсчёт столбов
• B. В гору пойдет!
• C. Развивающие игры
• D. Вечеринка в Нью-Йорке
• E. Сладкоежка
• F. Проще простого

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 1000/1000/1000/1000 ms. Memory limit 256000/256000/256000/256000 Kb.

Сладкоежка
Сладкоежка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
cake.in
вывод
cake.out

Тимофей — настоящий сладкоежка. Сегодня он купил большой и вкусный круглый торт с клубникой, чтобы полакомиться самому и угостить друзей.

Однако Тимофей угощает друзей очень изощренным способом. А именно, он отрезает кусочки с краев торта прямолинейными разрезами ножа. При этом, чтобы разрезы получились красивыми, нож нужно вести непрерывно, разрезы не должны друг друга пересекать, а закончить процесс отрезания нужно в начальной его точке. Более того, так как Тимофей — большой любитель клубники, то он хочет, чтобы все ягоды оказались внутри центрального куска тортика, который, конечно же, достанется ему самому.

Однако оказалось, что разрезать торт таким образом весьма непросто. Помогите Тимофею! Быть может, в награду он и вас угостит кусочком этого замечательного тортика.

Будем считать, что торт является кругом на плоскости, а ягоды представляют собой точки. Необходимо построить любой выпуклый многоугольник, вершины которого лежат на окружности, ограничивающей круг, а все заданные точки находятся внутри него или на его границе.

Входные данные

В первой строке входных данных содержатся четыре числа N, R, X, Y: количество ягод, радиус торта и координаты центра торта (1 ≤ N ≤ 100, 1 ≤ R ≤ 1 000, 0 ≤ |X|, |Y| ≤ 1 000). В следующих N строках содержатся описания ягод. Каждая ягода задается двумя числами xi, yi — своими координатами (0 ≤ |xi|, |yi| ≤ 1 000).

Выходные данные

В первой строке выходных данных выведите единственное число M — количество вершин в построенном вами многоугольнике (3 ≤ M ≤ 222). В следующих M строках выведите координаты вершин многоугольника, в порядке обхода против часовой стрелки.

Ваш ответ будет считаться верным, если все выведенные вами точки различны, действительно лежат на окружности, если они образуют выпуклый многоугольник, и если все ягоды лежат внутри или на границе многоугольника.

Проверяющая программа производит все проверки с точностью 10 - 6, в частности, независимо от того, сколько знаков вы выведите после десятичной точки, две вершины многоугольника будут считаться совпадающими, если они отличаются и по x-координате, и по y координате не более, чем на 10 - 6.

Примеры

Входные данные

Выходные данные

4 6 2 3

2 4

3 4

1 2

-4 3

4

-4.000000 3.000000

-2.242640 -1.242640

8.000000 3.000000

2.000000 9.000000

 

Для отправки решений необходимо выполнить вход.

www.contester.ru