Темы --> Информатика --> Алгоритмы --> Вычислительная геометрия --> Элементарная геометрия
---> 31 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#1179
Треугольник
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На координатной плоскости расположены равнобедренный прямоугольный треугольник ABC с длиной катета d и точка X. Катеты треугольника лежат на осях координат, а вершины расположены в точках: A (0,0), B (d,0), C (0,d).

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

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

Сначала вводится натуральное число d(не превосходящее 1000), а затем координаты точки X – два целых числа из диапазона от ­–1000 до 1000.

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

Если точка лежит внутри, на стороне треугольника или совпадает с одной из вершин, то выведите число 0. Если точка лежит вне треугольника, то выведите номер вершины треугольника, к которой она расположена ближе всего (1 – к вершине A, 2 – к B, 3 – к C). Если точка расположена на одинаковом расстоянии от двух вершин, выведите ту вершину, номер которой меньше.

Комментарии к примерам тестов

1. Точка лежит внутри треугольника.

2. Точка лежит вне треугольника и ближе всего к ней вершина A

3. Точка лежит на равном расстоянии от вершин B и C,в этом случае нужно вывести ту вершину, у которой номер меньше, т.е. выведено должно быть число 2

4. Точка лежит на стороне треугольника.

Примеры
Входные данные
5
1 1
Выходные данные
0
Входные данные
3
-1 -1
Выходные данные
1
Входные данные
4
4 4
Выходные данные
2
Входные данные
4
2 2
Выходные данные
0
#1208
Треугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

Недавно Петя, зайдя в класс, увидел, что на доске нарисовано n точек. Разумеется, он сразу задумался, сколько существует троек из этих точек, которые являются вершинами равнобедренных треугольников.

Требуется написать программу, решающую указанную задачу.

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

Входной файл содержит целое число n (3 ≤ n ≤ 1500). Каждая из последующих строк содержит по два целых числа – xi и yi – координаты i-ой точки. Координаты точек не превосходят 109 по абсолютной величине. Среди заданных точек нет совпадающих.

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

В выходной файл выведите ответ на задачу.

Разбалловка для личной олимпиады

Тесты 1-2 — из условия. Оцениваются в 0 баллов.

Тесты 3-13 — n не превосходит 500. Группа тестов оценивается в 40 баллов.

Тесты 14-28 — дополнительных ограничений нет. Группа тестов оценивается в 60 балла (вместе с предыдущими группами — 100 баллов).

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

Примеры
Входные данные
3
0 0
2 2
-2 2
Выходные данные
1
Входные данные
4
0 0
1 1
1 0
0 1
Выходные данные
4
#1317
Квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes
X1,Y1), (X2,Y2), (X3,Y3). Найти длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник так, чтобы все вершины треугольника находились внутри квадрата либо на его сторонах.

Составьте программу, которая по координатам вершин треугольника находит длину L стороны квадрата минимальной площади, в который можно поместить этот треугольник. L достаточно найти с точностью 10-4.

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

Файл содержит в одной строке действительные числа X1 Y1 X2 Y2 X3 Y3, разделенные пробелами, – координаты вершин треугольника (-10000 X1, Y1, X2, Y2, X3, Y3 10000).

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

Файл должен содержать одно число - длину L стороны искомого квадрата.

Примеры
Входные данные
0.0 0.0 1.1 0.0 0.0 1.1
Выходные данные
1.100000000
#1344
Многоугольники
  
ограничение по времени на тест
0.1 second;
ограничение по памяти на тест
64 megabytes

На плоскости задано такое множество из N многоугольников, что выполняются следующие условия:

  • никакие два многоугольника не имеют общих точек;
  • для каждого i –го многоугольника существует Pi многоугольников, внутри которых он находится, и N-1-Pi многоугольников, которые находятся внутри его, 0 ≤Pi≤N-1.

Напишите программу, которая для каждого многоугольника выдает количество многоугольников, внутри которых он находится.

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

Первая строка входного файла содержит целое число N — количество многоугольников, 3≤N≤100000. Следующие N строк файла описывают N многоугольников. (i+1)–ая строка файла описывает i–ый многоугольник. Первое целое число Ci — количество вершин многоугольника, 3≤Ci≤20. Последующие Ci пар чисел — координаты вершин многоугольника в порядке его обхода. Координаты вершин — целые числа, принадлежащие диапазону от -2 000 000 000 до 2 000 000 000.

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

Единственная строка выходного файла должна содержать N чисел: i–ое число строки должно быть Pi — количество многоугольников, внутри которых находится i–ый многоугольник.

Примеры
Входные данные
3
3 -2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2
Выходные данные
0 2 1
#1346
ВТО
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Территория Великой Треугольной Области (ВТО) представляет собой прямоугольный треугольник. Длины его катетов равны M и N государственных единиц длины (ГЕД). Правительство ВТО решило покрыть как можно большую часть территории области квадратными плитами размером 11 ГЕД. Плиты должны плотно прилегать друг к другу и к катетам ВТО. Разрезать плиты нельзя.

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

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

Напишите программу, которая по длинам катетов ВТО и вместимости контейнера находит количество плит, которые останутся на складе после осуществления проекта.

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

Единственная строка входного файла содержит три целых числа: M, N (2≤M, N≤2 000 000 000) и P (100≤P≤10 000).

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

Единственная строка выходного файла должна содержать целое число — количество неиспользованных плит из последнего контейнера.

Примеры
Входные данные
4 3 100
Выходные данные
97
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест