Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 54 55 56 57 58 59 60 >> Отображать по:
#451
Принадлежность точки выпуклому многоугольнику
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Задан многоугольник и точка. Нужно определить, лежит ли точка внутри этого многоугольника. В этой задаче многоугольник выпуклый.

Решите задачу быстрым методом

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

Сначала вводится число N (3<=N<=100). Далее идут N пар вещественных чисел, задающих координаты вершин многоугольника. Последние два вещественных числа задают координаты точки.

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

Выведите сообщение YES, если точка лежит внутри многоугольника, или NO в противном случае. Гарантируется, что точка не лежит на границе многоугольника.

Примеры
Входные данные
3
0 0
1 0
0 1
10 10
Выходные данные
NO
#452
Принадлежность точки произвольному многоугольнику
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Задан многоугольник и точка. Нужно определить, лежит ли точка внутри этого многоугольника. В этой задаче многоугольник невыпуклый.

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

Сначала вводится число N (3<=N<=100). Далее идут N пар вещественных чисел, задающих координаты вершин многоугольника. Последние два вещественных числа задают координаты точки.

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

Выведите сообщение YES, если точка лежит внутри многоугольника, или NO, если нет. Гарантируется, что точка не лежит на границе многоугольника.

Примеры
Входные данные
3
0 0
1 0
0 1
10 10
Выходные данные
NO
#453
Покрыть точки кругом
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Даны N точек. Требуется построить круг минимального радиуса такой, чтобы этот круг целиком покрывал все точки (допустимо, чтобы некоторые точки лежали на границе круга).

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

Сначала вводится  число N - количество точек, 3<=N<=100000. Далее идут N пар чисел, задающих координаты точек.  Координаты - вещественные числа.

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

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

Примеры
Входные данные
4
0 0 
6 0
6 8
0 8
Выходные данные
 3.00000000000000E+0000  4.00000000000000E+0000  5.00000000000000E+0000
#454
Преобразование системы координат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Есть две системы координат - первая и вторая. Вторая система устроена так, что ее центр в первой системе имеет координаты (A,B). Ее оси параллельны осям первой системы. При этом точка, которая во второй системе имеет координаты (1,0) в первой имеет координаты (C,B), а точка, имеющая во второй координаты (0,1) - координаты (A,D).

Дана точка, которая в первой системе имеет координаты X1,Y1.
Какие координаты она будет иметь во второй системе?
Какие координаты будет иметь точка в первой системе, если ее координаты во второй - X2, Y2?

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

Даны вещественные числа A, B, C, D, X1, Y1, X2, Y2.

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

Выведите координаты первой точки во второй системе и координаты второй точки - в первой. Все числа должны быть выведены не менее, чем с 3 знаками после десятичной точки.

Примеры
Входные данные
1 2 5 3
0 0 0 0
Выходные данные
-2.50000000000000E-0001 -2.00000000000000E+0000  1.00000000000000E+0000  2.00000000000000E+0000
#455
Торт для жюри
  

K членов Жюри Десятой Всероссийской олимпиады школьников по информатике решили отметить столь круглую годовщину в одном из лучших ресторанов на Невском проспекте. На десерт вниманию Жюри предложили торт, имеющий форму прямоугольной призмы с выпуклым N-угольником в основании. Жюри вооружается десертными ножами и собирается справедливо разделить торт на K частей равного объема. Ножами можно проводить прямые вертикальные разрезы от одной границы торта до другой; различные разрезы могут иметь общие точки лишь в своих концевых вершинах.

Напишите программу, помогающую членам Жюри построить требуемые K-1 разрезов.

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

В первой строке входных данных содержатся два целых числа K и N (1 <= K, N <= 50). Далее следуют N пар вещественных чисел - координаты последовательно расположенных вершин N-угольника.

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

Каждый из K-1 разрезов в выходных данных должен быть представлен четверкой вещественных чисел с не менее чем 10 знаками после запятой - координатами концов соответствующего разреза. Все числа должны быть разделены пробелами и/или символами перевода строки.

Примеры
Входные данные
2 3
1 0
0 0
0 1
Выходные данные
 1.0000000000E+00  0.0000000000E+00  0.0000000000E+00  5.0000000000E-01
Страница: << 54 55 56 57 58 59 60 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест