--->
144 задач
<---
Источники
#1208
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Региональный этап,
2009,
1 день,
Задача D
]
ограничение по времени на тест
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
#1244
Темы:
[Элементарная геометрия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.
На плане леса все деревья изображаются кругами. Никакие два круга не пересекаются и не касаются друг друга. Требуется по этому плану определить, является ли лес дремучим.
Входные данные
Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.
Выходные данные
В первой строке выходного файла должно содержаться сообщение YES, если лес является дремучим, и NO иначе. Во втором случае вторая строка выходного файла должна содержать координаты двух точек, через которые проходит просека. Все координаты нужно выводить с восемью знаками после десятичной точки, координаты не должны превышать 2000, и расстояние между выданными точками должно быть не меньше 100.
Примеры
Входные данные
3
0.00 30.00 25.00
0.00 -30.00 25.00
40.00 0.00 16.00
Выходные данные
NO
-833.3333340000 -552.7707973875
833.3333340000 552.7707973875
Входные данные
3
0.00 30.00 29.00
0.00 -30.00 29.00
40.00 0.00 19.00
Выходные данные
YES
#1317
Темы:
[Элементарная геометрия]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
8 megabytes
Составьте программу, которая по координатам вершин треугольника находит длину 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
Выбрано
:
|