Тема: Triangles
Вам дано (N<=5000) точек (xi,yi). Надо найти количество правильных треугольников с разными вершинами.
Ограничение по времени 2 секунды
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Triangles
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Вам дано (N<=5000) точек (xi,yi). Надо найти количество правильных треугольников с разными вершинами.
Ограничение по времени 2 секунды
O(N^2 * log(N)) ?
Перебираем пару точек, по ней строим два варианта третьей точки, и ищем эти две точки среди всех данных.
Да, быстрее N^2 logN чето не получается придумать. Хотя для 5000 многовато получается. Возможно, предполагается, что это решение надо хорошенько протвикать и оно пройдёт
Если точки целочисленны, можно их искать в хеш-таблице за O(1)
Вроде как правильных треугольников с целочисленными координатами не существует.
не существует)
а задачка с области), тока там вроде 1500 было.
Alexey
Точно Пусть первая вершина в (0;0), вторая - в (x;y), тогда третья должна получаться поворотом вектора (x;y) на 60 градусов, и в результате неизбежно появится sqrt(3).
областная олипиады по информатике)
первый тур)
2009го года)
нет, эти задачки везде были)
Ну, я, например, московская. И писал московскую, собственно)
Ясн ) Забыл, что с этого года на область задачи присылаются одинаковые для всех
кстати, если не лень, то
http://e-maxx.ru/forum/viewtopic.php?id=30
А точное условии задачи вот такое:
Пример
E.in
3
0 0 0 3 4 0
E.out
1
--------------
E.in
4
0 0 0 1 1 0 0 -2
E.out
2
-------------
Задача E Треугольник
Вам даны координаты N различных точек. Требуется вычислить, сколько различных прямо-
угольных треугольников можно составить из заданных точек, используя их в качестве вершин
треугольников. Треугольники считаются разными, если у них различна хотя бы одна вершина.
Формат входных данных
Первая строка входного файла содержит число N (1 ? N ? 5000). Следующие N строк содержат
по два целых числа - координаты точек. Координаты точек - целые числа, по абсолютному зна-
чению не превосходящие 10000. Числа в строках разделены пробелами.
Формат выходных данных
Выходной файл должен содержать одно целое неотрицательное число - количество прямоуголь-
ных треугольников.
Прямоугольный и правильный треугольники - несколько разные понятия)
Могу предложить решение за n^2 log n (для прямоугольных 3-ков):
Фиксируем вершину при прямом угле (назовем ее центр). Сортируем все точки по полярному углу относительно центра. Далее методом 2-х указателей ищем для каждой точки такую, что ориентированный угол, который составляют эти 2 точки и центр равен 90 градусов. Все точки, которые лежат на одном луче (с началом в центре) надо предварительно выделить в группы.
n^2 log n при n = 5000 выглядит малореалистично
Ну в принципе это решение нетрудно довести до чистого квадрата хеш-таблицами (вместо сортировки считать количество точек с нужным углом, а вместо дабловых углов рассматривать целочисленные радиус-вектора, нормированные по gcd), правда, у меня всё равно сомнения, что это уложится
Странно, что эту задачу предложили на области в этом году. Она же вроде была в 2007 (+-1 год) году предложена на хорватском COCI. Называлась Pravokutni вроде. И вот там-то как раз были ограничения N от 1 до 1500. В авторском разборе три решения N^2*logN. Ну если так подумать, то такая асимптотика даст 3*10^8 операций в худшем случае (он даже и недостижим). На полуфинале такое количество операций над целыми проходило за 1 секунду.
Alexey
Точно Пусть первая вершина в (0;0), вторая - в (x;y), тогда третья должна получаться поворотом вектора (x;y) на 60 градусов, и в результате неизбежно появится sqrt(3).
Задача: доказать что при всех N кроме 4 правильных N-угольников с целыми вершинами не существует.
Не программистская, но довольно интересная...
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Triangles