Float free solution to Advent Day 10

10-integral.cpp

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

bool cmp(const pair<int, int>& u, const pair<int, int>& v) {
  bool u_side = make_pair(u.first, -u.second) <= make_pair(0, 0);
  bool v_side = make_pair(v.first, -v.second) <= make_pair(0, 0);
  if (u_side != v_side) {
    return v_side;
  }

  return 1ll * u.first * v.second - 1ll * u.second * v.first > 0;
}

int main() {
  int N = 0;

  vector<pair<int, int> > A;
  for (string s; cin >> s; N++) {
    for (size_t j = 0; j < s.size(); j++) {
      if (s[j] == '#') {
        A.push_back(make_pair((int)j, N));
      }
    }
  }

  pair<int, int> besti;
  map<pair<int, int>, set<int> > best;
  for (auto i : A) {
    map<pair<int, int>, set<int> > res;
    for (auto j : A) {
      if (i == j) continue;

      int dx = j.first - i.first;
      int dy = j.second - i.second;
      int g = gcd(abs(dx), abs(dy));
      
      res[make_pair(dx / g, dy / g)].insert(g);
    }
    if (best.size() < res.size()) {
      best = res;
      besti = i;
    }
  }

  A.clear();
  for (auto i : best) {
    A.push_back(i.first);
  }

  sort(A.begin(), A.end(), cmp);

  cout << A.size() << endl;
  for (auto i : A) {
    cout << i.first << ", " << i.second << endl;
  }

  auto dir = A[199];
  int g = *best[dir].begin();
  cout << dir.first * g + besti.first << ", " << dir.second * g + besti.second << endl;

  return 0;
}