Настройки поиска

Не стоит пока ее обсуждать, см. http://www.e-olimp.com/competitions/136 (задача O)

Если сортировать по arctan(x/y), легко получить проблемы с точностью, т.к. arctan - очень неточная штука, особенно при y->0. acrtan2(y, x) чуть лучше, но на многих задачах все равно не поможет. Гораздо лучше сортировать компаратором на основе векторного произведения. Для начала надо проверить, что вектора a и b находятся в одной полуплоскости. Если это не так, то их легко между собой сравнить. Иначе же считают что a < b если [a x b] > 0. Такой компаратор сравнивает вектора в целых числах и принципиально не может иметь проблем с точностью

Можно за O(n^2*log(n)), если в ней n ненулевых элементов, с помощью веселого дерева отрезков

Вообще, есть общий полиномиальный алгоритм для подсчета количества паросочетаний в планарном графе, правда к этой зададаче он не подходит (сложность порядка O(n^3)*(сложность длинного умножения n-битных чисел), где n - количество вершин в графе)

Спасибо)

Ну, на онсайте кластером особо не попользуешься

см. http://e-maxx.ru/forum/viewtopic.php?id=38

Да, я хотел сказать по автомату)))
Как решать массивом не очень понятно

n^2 log n при n = 5000 выглядит малореалистично

Эту задачу можно решать специальным деревом отрезков за O(n*log n) памяти и препроцессинга и O(log^3 n) на запрос.
Идея такая: в вершине дерева будем хранить соответствующий отрезок отсортированным. Тогда на каждый запрос надо найти разбиение запрашиваемого отрезка на не более O(log n) отрезков из дерева и найти ответ на запрос бинарным поиском (количество элементов менбших данного в отсортированном списке ищется еще одним бинарным поиском)