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

Question

Учитывая список координат в first quadrant, вычислите, сколько прямоугольных треугольников может быть сформировано из них, у которых одна сторона параллельна x-axis, а одна сторона параллельна y-axis.

Недавно я принял участие в соревновании по программированию, в частности INOI ( Индийская национальная олимпиада по информатике ), и это был первый из двух вопросов в статье.

В принципе, я полагал, что любые 3 точки типа (a,y) (x,y) (x,b) образуют такой треугольник, но не могут справиться с чем-то лучше, и в конце просто написал наивный O (n^ 3) решение ( и все мои друзья ).

Кто-нибудь может предложить лучший способ?

И, пожалуйста, ЭТО НЕ РАБОТАЕТ.

Answer 1

Позволяет numX[i] = how many points have i as their X coordinate и numY[i] = how many points have i as their Y coordinate.

Мы посчитаем, сколько треугольников с требуемым свойством существует для определенной точки p.Без ограничения общности можно предположить, что p - это точка, в которой треугольники образуют прямой угол.

Для этого нам понадобится точка с одинаковой координатой Y и точкой с одинаковойX координата.А как насчет этого алгоритма:

compute numX and numY in O(n).
num = 0
for each point p in the given list of points
    num += (numX[p.X] - 1)*(numY[p.Y] - 1)

output num

По сути, мы можем объединить каждую точку с одинаковой X координатой с каждой точкой с одинаковой Y координатой, чтобы получить нужный треугольник.Мы вычитаем 1, чтобы не считать p.

Это будет выполняться в O(n).

Answer 2

Да, я согласен с IVlad там. входные данные могут быть непосредственно сохранены в массиве 2 * N, и в то же время счетчик для каждого x и y должен быть сохранен в numX и numY ... тогда это просто wat IVlad сказал ...