# Count number of isosceles triangles in a set of points

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?

# 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.

• It isn't $(n-1)!$ that you need to add, it's $n \choose 2$, or $n * (n-1) / 2$. Also, you can avoid double counting equilateral triangles by simply not including previously seen vertices when computing the list of all distances for a vertex.
– JS1
Commented Aug 28, 2015 at 3:11
• @JS1 Uh, your formula is indeed the right one, that's what I got for only checking with a small number of points, thanks. That said, I thought of removing the previously visited vertices as well, but a same vertex can be in several isoceles triangles that just happen to share a side, so I don't think that it will work. Commented Aug 28, 2015 at 8:01
• You're right on that second point. I suppose you could keep a HashMap of triangles created, and check for uniqueness.
– JS1
Commented Aug 28, 2015 at 19:25
• @JS1 Probably, but thay may increase the complexity. We currently store only a count, but now we'd have to store points and check for uniqueness. Well, it might not increase the complexity per se, but it'll be a noticeable constant factor :/ Commented Aug 28, 2015 at 19:56