Triangles

O(N^2 * log(N)) ?
Перебираем пару точек, по ней строим два варианта третьей точки, и ищем эти две точки среди всех данных.

Если точки целочисленны, можно их искать в хеш-таблице за O(1)

не существует)
а задачка с области), тока там вроде 1500 было.

chum
Ну для 1500 с логарифмом точно пройдёт.
А что за область?

Не, я имею в виду, область какая?

Саратов что ле? )))

Ясн ) Забыл, что с этого года на область задачи присылаются одинаковые для всех

А точное условии задачи вот такое:

Пример
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 градусов. Все точки, которые лежат на одном луче (с началом в центре) надо предварительно выделить в группы.

Ну в принципе это решение нетрудно довести до чистого квадрата хеш-таблицами (вместо сортировки считать количество точек с нужным углом, а вместо дабловых углов рассматривать целочисленные радиус-вектора, нормированные по gcd), правда, у меня всё равно сомнения, что это уложится