Count number of isosceles triangles in a set of points

Question

Given a set of points, what is the number of isosceles triangles that can be formed with the combinations of all points in the set?

It is certain that 3 collinear points never exists in the set.

#include <stdio.h>

typedef unsigned long long llu;

typedef struct {
    llu x,y;
}point_t;

inline llu distance_p(point_t &p1,point_t &p2)
{
    return (p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y);
}

int main(void){
    llu n;
    point_t ps[1000];
    while (scanf("%llu",&n), n) {
        for (int i = 0; i < n; ++i)
            scanf("%llu %llu",&ps[i].x,&ps[i].y);

        llu ans = 0;
        for (llu i = 0,a,b,c; i < n; ++i) {
            for (llu j = i + 1; j < n; ++j) {
                for (llu k = j + 1; k < n; ++k) {
                    a = distance_p(ps[i], ps[j]);
                    b = distance_p(ps[j], ps[k]);
                    c = distance_p(ps[k], ps[i]);

                    //at least two side equals
                    if(a == b || b == c || c == a){
                        ++ans;
                    }
                }
            }
        }
        printf("%llu\n",ans);
    }
}

But this is slow: \$O(n^3)\$. How can I improve my code?

Answer 1

Try another algorithm

Instead of considering triangles, you could simply consider lines starting from a point.

For each point, compute the distance between this point and every other point; you will get a number of distances.

Now, for every distance from a point, count the number \$n\$ of equal distances, and add \$n*(n-1)/2\$ to the number of isoceles triangles. If you use an std::unordered_map<unsigned long long, unsigned> to count the number of occurrences of every distance from a point, it should give you a \$O(n^2)\$ algorithm, if I'm not mistaken.

Note: this method might count the same triangle several times if a triangle happens to be equilateral. Unfortunately, I don't see a simple way to circumvent this problem.

C++ pedantry

I talked about the math first since it's what really matters, but honestly, your C++ isn't the prettiest C++ around, so here we go for the C++ review:

• Please don't use typedef unsigned long long llu;. Even if it's long to write, llu doesn't convey any meaning to anyone reading it. Type the full name and people will know out-of-the-box what type they are using.

• distance_p looks like it computes the distance between p1 and p2, but it actually computes the the squared distance between them. Make that clear by naming the function squared_distance.

• Also, distance_p does not alter its parameter. Therefore, pass const references instead of simple ones:

  inline unsigned long long squared_distance(const point_t &p1, const point_t &p2)
  {
      return (p2.x - p1.x)*(p2.x - p1.x) + (p2.y - p1.y)*(p2.y - p1.y);
  }
  

• You don't need to use typedef like it is done in C to write point_t instead of struct point_t. In C++, an equivalent typedef is done automagically by the compiler. Simply declare your struct like this:

  struct point_t {
      unsigned long long x, y;
  };
  

• When using components from the standard library, try to always prefix them with std::, even in they come from the C standard library (std::printf, std::scanf, etc...). Prefixing them may help to avoid name clashes and make it easier to search for standard library components in your code.

• Try not to put everything in main. Here, you can easily put the algorithm which looks for isoceles triangles in its own function and let main handle only the input & output operations. Splitting code into small logical bricks instead of tightly coupled ones is known as separation of concerns.

Putting it all together

Since there are many things to take into account. I decided that I could as well show you how I would have implemented count_isoceles_triangles as described using C++11 (that's not exactly how I would have done it, but it's closer to it than what you currently have):

struct point_t
{
    unsigned long long x;
    unsigned long long y;
};

unsigned long long squared_distance(const point_t &p1, const point_t &p2)
{
    unsigned long long a = p2.x - p1.x;
    unsigned long long b = p2.y - p1.y;
    return a*a + b*b;
}

template<std::size_t N>
unsigned count_isoceles_triangles(const std::array<point_t, N> points)
{
    unsigned nb_triangles = 0;

    for (const point_t& p1: points)
    {
        std::unordered_map<unsigned long long, unsigned> distances;
        for (const point_t& p2: points)
        {
            unsigned long long dist = squared_distance(p1, p2);
            distances[dist] += 1;
        }

        for (auto&& dist: distances)
        {
            unsigned count = dist.second;
            nb_triangles += count * (count - 1) / 2;
        }
    }

    return nb_triangles;
}

Note that there are still some additional differences: I used std::array since it's not easy to pass a C array to a function correctly. Also, I didn't check whether p1 == p2 before counting the distances, but it's also something that should be done.