USACO 2.1 Ordered Fraction

Brutal force search.

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
  if (a < b)
    swap(a, b);

  while (b) {
    int t = a % b;
    a = b;
    b = t;
  }

  return a;
}

int main() {
  ifstream fin("frac1.in");
  ofstream fout("frac1.out");

  int N;
  fin >> N;

  vector<pair<int, int>> vec;

  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= i; ++j) {
      if (gcd(j, i) == 1)
        vec.emplace_back(make_pair(j, i));
    }
  }

  sort(vec.begin(), vec.end(), [] (const pair<int, int> &lhs,
                                   const pair<int, int> &rhs) {
    return (static_cast<double>(lhs.first) / static_cast<double>(lhs.second)) <
    (static_cast<double>(rhs.first) / (static_cast<double>(rhs.second)));
  });

  for (auto &item : vec)
    fout << item.first <<  "/" << item.second << endl;
  return 0;
}