Помітимо, що в повному графі, де є усі можливі ребра, умова про відповідність найкоротших шляхів у графі з евклідовою відстанню виконується. Проте ми можемо видалити ребро між вершинами та , якщо існує вершина , яка лежить на відрізку між точками та . Видалення таких ребер не змінить найкоротші шляхи у графі. Можна довести, що будь-які інші ребра видаляти не можна, оскільки в такому випадку найкоротший шлях між відповідними вершинами не буде рівним їхній евклідовій відстані.
Для того аби порахувати відповідь швидко, ми для кожної вершини дивимось скільки є унікальних напрямків до інших вершин. Напрямки можна зберігати як , де та взаємнопрості, маючи такі пари нам треба порахувати швидко кількість унікальних.
Складність O(n^2 \cdot \log n).