Counting ways to choose vertices that form a right triangle

Question

Croatian Open Competition in Informatics, contest 3, December 8, 2007
4. DEJAVU

\$N\$ points are placed in the coordinate plane.

Write a program that calculates how many ways we can choose three points so that they form a right triangle with legs parallel to the coordinate axes.

A right triangle has one 90-degree internal angle. The legs of a right triangle are its two shorter sides.

Input

The first line of input contains the integer \$N\$, the number of points, where \$3 \le N \le 100000\$.

Each of the following \$N\$ lines contains two integers \$X\$ and \$Y (1 \le X, Y \le 100000)\$, the coordinates of one point.

No points will share the same pair of coordinates.

Output

Output the number of triangles.

Sample input

3
4 2
2 1
1 3

Sample output

0

This is my solution:

For every point, I checked other point. If two points had matching x coordinates and different y coordinates, I looked through the points to find a point with same y coordinate as the new point and different x. If found, I checked if the right angled hypotenus checks out in the three points.

Similarly, I repeated a modification of this for two points with matching y coordinates and different x.

The program gets the right result, but needs far too long.

#include<iostream>
#include<cmath>
using namespace std;

/*
double distwithoutroot(int x1, int y1, int x2, int y2) {
    //cout << "Got here for values " << x1 << y1 << x2 << y2 << endl;
    int xdist = pow((x2 - x1),2);

    int ydist = pow((y2 - y1),2);

    return  xdist + ydist;

}

*/

int main() {
    int noofpoints;
    int conditionnotsatisfied = 0;
    cin >> noofpoints;
    int xs[100000];
    int ys[100000];
    int count = 0;

    for (int i = 0; i < noofpoints; i++) {
        cin >> xs[i] >> ys[i];
    }

    for (int i = 0; i < noofpoints; i++) {
        int main_x_point = xs[i];
        int main_y_point = ys[i];

        for (int j = 0; j < noofpoints; j++) {
            int checkmatchx = xs[j];
            int checkmatchy = ys[j];

            if (main_x_point == checkmatchx && main_y_point != checkmatchy) {

                for (int k = 0; k < noofpoints; k++) {
                    int secondcheckx = xs[k];
                    int secondchecky = ys[k];

                    if (checkmatchy == secondchecky && checkmatchx != secondcheckx) {
                       // int hypotenus = distwithoutroot(main_x_point, main_y_point, secondcheckx, secondchecky);
                        //hypotenus = pow(hypotenus,2);
                        //int perpendicular = distwithoutroot(main_x_point, main_y_point, checkmatchx, checkmatchy);
                        //perpendicular = pow(perpendicular,2);
                        //int base = distwithoutroot(secondcheckx, secondchecky, checkmatchx, checkmatchy);
                        //base = pow(base,2);
                        //if (hypotenus== ( perpendicular+ base )) {
                            count += 1;
                            //cout << main_x_point << " " << main_y_point << "  " << checkmatchx << " " << checkmatchy << "  " << secondcheckx << " " << secondchecky << endl;

                            //xs[i] = 0;
                            //ys[i] = 0;
                        //}


                    }

                }


            }

            else if (main_y_point == checkmatchy && main_x_point != checkmatchx) {

                for (int k = 0; k < noofpoints; k++) {
                    int secondcheckx = xs[k];
                    int secondchecky = ys[k];

                    if (checkmatchx == secondcheckx && checkmatchy != secondchecky) {
                    //    int hypotenus = distwithoutroot(main_x_point, main_y_point, secondcheckx, secondchecky);
                        //hypotenus = pow(hypotenus,2);
                      //  int base = distwithoutroot(main_x_point, main_y_point, checkmatchx, checkmatchy);
                        //base = pow(base,2);
                        //int perpendicular = distwithoutroot(secondcheckx, secondchecky, checkmatchx, checkmatchy);
                        //perpendicular = pow(perpendicular,2);
                        //if (hypotenus == (perpendicular + base)) {
                            count += 1;
                            //cout << main_x_point << " " << main_y_point << "  " << checkmatchx << " " << checkmatchy << "  " << secondcheckx << " " << secondchecky << endl;
                            //xs[i] = 0;
                            //ys[i] = 0;
                    //    }
                    }
                }
            }


        }

    }

    //cout << "count value after first check " << count << endl;
    //cout << "Condition not satisfid " << conditionnotsatisfied << endl;
/*
    for (int i = 0; i < noofpoints; i++) {
        int main_x_point = xs[i];
        int main_y_point = ys[i];

        for (int j = 0; j < noofpoints; j++) {
            int checkmatchx = xs[j];
            int checkmatchy = ys[j];

            if (main_y_point == checkmatchy && main_x_point != checkmatchx) {

                for (int k = 0; k < noofpoints; k++) {
                    int secondcheckx = xs[k];
                    int secondchecky = ys[k];

                    if (checkmatchx == secondcheckx && checkmatchy != secondchecky) {
                        int hypotenus = distwithoutroot(main_x_point, main_y_point, secondcheckx, secondchecky);
                        //hypotenus = pow(hypotenus,2);
                        int base = distwithoutroot(main_x_point, main_y_point, checkmatchx, checkmatchy);
                        //base = pow(base,2);
                        int perpendicular = distwithoutroot(secondcheckx, secondchecky, checkmatchx, checkmatchy);
                        //perpendicular = pow(perpendicular,2);
                        if (hypotenus == (perpendicular + base)) {
                            count += 1;
                            //cout << main_x_point << " " << main_y_point << "  " << checkmatchx << " " << checkmatchy << "  " << secondcheckx << " " << secondchecky << endl;
                            //xs[i] = 0;
                            //ys[i] = 0;
                        }
                    }
                }
            }
        }

    }
    */

    cout << count/2;
}

Answer 1

Implementation issues

• using namespace std; is discouraged.

• Placing such big arrays as xs and ys on the stack can cause stack overflows. For example, on 64-bit Windows their combined size would be \$2 * 8 * 100000 = 1600000\$ Bytes (= 1.6 MB), which is above the default Windows stack size of 1 MiB. (YMMV for other platforms.)

• All those comments are distracting and don't provide any value to the reader.

• Some parts of the code could be refactored out into functions and reused, which would increase readability by reducing nesting.

• Arrays by themselves aren't the right data structure for this problem.

Choosing the right data structure/algorithm

The implementation tries to find 3 matching points by combining every point with every possible other point, and if a match was found, again with every other possible point, resulting in a runtime of \$\mathcal{O}(n^3)\$.

This is bad. But we can improve!

Algorithm

A better algorithm looks like this:

1. Create sets of points which have the same x-coordinate.

2. Create a histogram over the y-coordinates.

3. For each set \$p\$ created in step 1:

   • If there are less than 2 points in \$p\$, then there cannot be any triangle with a leg along that x-coordinate.

   • Foreach y-coordinate of the points in \$p\$ check if there is at least another point on the same y-coordinate (by retrieving the count \$q\$ using the histogram created in step 2).

     If that's the case, then there can be \$(\lvert p\rvert - 1) * (q - 1)\$ right triangles at this point.

Data structures

Instead of treating each point as a whole, we split it up into its coordinates in order to create a std::unordered_map<int, std::unordered_set<int>>, (x-coordinate -> set of y-coordinates) to store the results of step 1.

For the histogram (step 2), a std::unordered_map<int, int> (y-coordinate -> counter) would be the obvious choice.

Both datastructures chosen (std::unordered_map and std::unordered_set) have \$\mathcal{O}(1)\$ lookup cost and amortized \$\mathcal{O}(1)\$ insertion.

Complexity

Since step 1 and step 2 can be done during the same pass over the input data, we effectivly only need 2 passes over the whole set of points.

The first pass inserts all points into points (1 lookup/insertion, plus 1 insertion into the returned set) and adds a count to the histogram (1 insertion/lookup).

• std::unordered_map lookup/insertion: \$\mathcal{O}(1)\$ (amortized for insertion)

• std::unordered_set insertion: \$\mathcal{O}(1)\$ amortized.

Total complexity of pass 1: \$\mathcal{O}(n)\$

In the second pass, we iterate over the x-coordinates in points (\$\mathcal{O}(1)\$ per outer iteration step) and then the corresponding y-coordinates (\$\mathcal{O}(1)\$ per inner iteration step).

Since these iteration steps are basically recreating all the points from the input, there are \$\mathcal{O}(n)\$ inner iteration in total, each with a complexity of \$\mathcal{O}(1)\$, with a combined complexity of \$\mathcal{O}(n)\$.

For each outer iteration step we performa a call to std::unordered_set::size (\$\mathcal{O}(1)\$).

For each inner iteration step we perform 1 lookup in the histogram (\$\mathcal{O}(1)\$) plus some minimal arithmetic (\$\mathcal{O}(1)\$).

Total complexity of pass 2: \$\mathcal{O}(n)\$

Example implementation of the algorithm

#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <numeric>
#include <stdexcept>

class triangle_finder {
    std::unordered_map<int, std::unordered_set<int>> points;
    std::unordered_map<int, int> histogram;

public:
    int count_axis_aligned_triangles() noexcept {
        auto count = 0;

        for(const auto& [x, y_coords] : points) {
            count = std::accumulate(
                std::begin(y_coords),
                std::end(y_coords),
                count,
                [&, num_points_x = y_coords.size()](auto count, auto y) {
                    return count + (num_points_x - 1) * (histogram[y] - 1);
                });
        }

        return count;
    }

    friend std::istream& operator>>(std::istream&, triangle_finder&) noexcept;
};

std::istream& operator>>(std::istream& stream, triangle_finder& p) noexcept {
    auto num_points = 0;
    stream >> num_points;

    for(auto i = 0; i < num_points; ++i) {
        int x, y;
        if(!stream >> x >> y) return stream;

        p.points[x].insert(y);
        ++p.histogram[y];
    }

    return stream;
}

int main() {
    triangle_finder p{};

    if(std::cin >> p) {
        std::cout << p.count_axis_aligned_triangles();
    } else {
        std::cerr << "Error: Couldn't parse input\n";
        return 1;
    }
}

Answer 2

First, the algorithm is unacceptable. We can do much better than completely dumb brute-force which results in \$O(n^3)\$.

1. Get all points.
2. Sort them by x-coordinate then y-coordinate, discarding duplicate points.
3. Make a histogram of the y-coordinates.
4. Go through the array and find runs of points with the same x-coordinate:
   1. For every y-coordinate, add \$(size\_of\_run - 1) * (points\_with\_y - 1)\$ to the result.

That is \$O(n * log(n))\$, due to sorting.

---

Now, let's look how you coded your solution:

1. Don't leave commented-out code around. It seriously obscures things. Your version-control-system is for recovering old versions when needed. You use one, right?
2. Keep your line-length reasonable. Horizontal scrolling is hard work and murder on reading-speed.
   Yes, you only have comments off-screen to the right, but how would anyone know for sure beforehand?
3. Never import a namespace that isn't designed for it. Even if you don't have any name-conflicts now, it's only a question of time and luck. Read "Why is “using namespace std;” considered bad practice?" for the details.
4. What can go wrong, will go wrong, earlier or later. So don't assume input will succeed, verify it. Or at least ask for exceptions on error, that's acceptable for such a small program.
5. Consider using std::vector to avoid the arbitrary limit. Which you should have verified too, even though it was in the requirements. Anyway, I'm astounded those automatic arrays don't blow the Default stack's limit.
6. Use your own point-class, or better yet std::pair. That makes it far easier than manipulating component-arrays in parallel.
7. Consider extracting a few well-named functions, both for organisation and possible re-use.

Answer 3

Headers and namespaces

#include <cmath>

Not used - it can be omitted

using namespace std;

Don't bring in names from big and expanding namespaces such as std. Instead, import just the names you need, into the smallest reasonable scope, or explicitly qualify them - the name std is so short for a reason!

Program structure

You will probably find it helpful to separate the reading of the problem set and the writing of the output from the actual calculation of the number of right-angled triangles. Putting the computation into its own function will then allow you to test it with known input sets, as a form of unit test.

Data structure

Currently, we're using two parallel arrays of x and y coordinates. It's likely to be easier to follow, and we'll get better locality of reference, if we hold x,y pairs together:

struct Point
{
    int x;
    int y;
}

(I'll work with int here; I'll leave it as an exercise to select arithmetic types that are portably large enough to represent all values).

Algorithm

At present, we seem to be only finding triangles that are oriented parallel to the x and y axes. This will miss triangles at other angles, such as {(0,0), (1,1), (1,-1)} for example.

A more reliable way to detect triangles is to use Pythagoras' Theorem - a triangle is right-angled if the square of one of the sides is equal to the square of the other two:

#include<iostream>
#include<vector>


struct Point
{
    int x;
    int y;
};

int square_distance(const Point p, const Point q)
{
    const auto dx = p.x - q.x;
    const auto dy = p.y - q.y;
    return dx * dx + dy * dy;
}

bool is_right_triangle(const Point p, const Point q, const Point r)
{
    const auto a = square_distance(p, q);
    const auto b = square_distance(q, r);
    const auto c = square_distance(r, p);
    return a == b + c
        || b == c + a
        || c == a + b;
}

int count_right_triangles(const std::vector<Point>& points)
{
    int count = 0;
    for (auto i = points.begin();  i != points.end();  ++i) {
        for (auto j = points.begin();  j != i;  ++j) {
            for (auto k = points.begin();  k != j;  ++k) {
                count += is_right_triangle(*i, *j, *k);
            }
        }
    }
    return count;
}

int main() {
    int n_points;
    std::cin >> n_points;
    if (!std::cin)
        return 1;

    std::vector<Point> points;
    points.reserve(n_points);

    for (int i = 0; i < n_points; i++) {
        Point p;
        if (std::cin >> p.x >> p.y) {
            points.push_back(p);
        } else {
            return 1;
        }
    }

    std::cout << count_right_triangles(points);
}

Alternative algorithm

Another approach we could consider is to record the angles of all connecting pairs of points, as a multimap from each angle to the points it contains. Then inspect the keys for angles separated by 90°, and for each of those angles count the points common to both sets, and use those numbers to compute the triangles. You'll probably want a rational-number class to represent the angles as their tangents (floating-point may introduce rounding errors that could affect the result).