Counting triangles for http://math.stackexchange.com/q/624106/35416

17gon.txt

[[-268976423, -1041068828],
 [287927556, -823085024],
 [582279163, -505571674],
 [819462839, -173345367],
 [1052940007, 159999717],
 [905221059, 588231118],
 [594051833, 782699842],
 [405217384, 822595358],
 [94700867, 805634136],
 [-175966121, 643525529],
 [-460676235, 413867560],
 [-926177448, -80668983],
 [-1055777146, -428567710],
 [-1044355178, -664117664],
 [-1020973803, -815704805],
 [-909166799, -906166019],
 [-612815843, -976687827]]
// 979 triangles
[[126537253, 433736357],
 [-304104591, 256672119],
 [-515385287, 162077668],
 [-737223315, -32806045],
 [-942490812, -244361324],
 [-1018173054, -485175037],
 [-975290575, -705564913],
 [-819111115, -918720814],
 [-615777584, -963966533],
 [-52264557, -1024938838],
 [683870185, -1025494554],
 [904460732, -711503439],
 [1058758128, -290245316],
 [1053745097, -101763937],
 [795157670, 257850919],
 [524962396, 422078798],
 [374248501, 451667475]]
// 981 triangles

triangleCount.cc

#include <string>
#include <iostream>
#include <sstream>
#include <random>

#include <CGAL/Gmpz.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

#define DBG(x) std::cerr << x << std::endl

typedef CGAL::Gmpz ZZ;
typedef CGAL::Homogeneous<ZZ> Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits;
typedef Kernel::Point_2 Point;
typedef Kernel::Segment_2 Segment;
typedef CGAL::Arrangement_2<Traits> Arrangement;

class RandomPointGen {
private:
  constexpr static int limit = 1 << 30;
  std::uniform_int_distribution<> dist;
  std::mt19937 rnd;
public:
  RandomPointGen() : dist(-limit, limit), rnd(1234) { }
  Point operator()() {
    int x = dist(rnd);
    int y = dist(rnd);
    return Point(ZZ(x), ZZ(y));
  }
};

static unsigned run(unsigned short n, unsigned long num_iterations) {
  unsigned long iteration = 0;
  RandomPointGen randomPoint;
  std::vector<Point> corners(n);
  Arrangement arr;
  unsigned best = 0;
  while (num_iterations == 0 || ++iteration <= num_iterations) {
    corners[0] = randomPoint();
    corners[1] = randomPoint();
    for (unsigned short i = 2; i != n; ++i) {
      Point q;
      unsigned short j = i;
      while (j == i) {
        q = randomPoint();
        for (unsigned short k = 0; k != i; ++k) {
          if (CGAL::left_turn(corners[k], q, corners[(k + 1)%i])) {
            if (j == i) {
              j = k;
            }
            else {
              j = i;
              break;
            }
          }
        }
      }
      corners.insert(corners.begin() + j + 1, q);
    }
    arr.clear();
    for (unsigned short i = 0; i != n; ++i) {
      for (unsigned short j = i + 1; j != n; ++j) {
        CGAL::insert(arr, Segment(corners[i], corners[j]));
      }
    }
    unsigned triangles = 0;
    for (Arrangement::Face_iterator i = arr.faces_begin(), e = arr.faces_end();
         i != e; ++i) {
      if (!i->has_outer_ccb()) continue;
      if (CGAL::circulator_size(i->outer_ccb()) == 3)
        ++triangles;
    }
    if (best < triangles) {
      best = triangles;
      for (unsigned short i = 0; i != n; ++i)
        std::cout << (i ? ",\n " : "[")
                  << '[' << corners[i].x().numerator() << ", "
                  << corners[i].y().numerator() << ']';
      std::cout << "]\n// " << triangles << " triangles" << std::endl;
    }
  }
  return best;
}

int main(int argc, char** argv) {
  unsigned short n = 17;
  unsigned long m = 0;
  if (argc >= 2) {
    std::istringstream(argv[1]) >> n;
  }
  if (argc >= 3) {
    std::istringstream(argv[2]) >> m;
  }
  std::cout << "n = " << n << ", ";
  if (m == 0)
    std::cout << "infinite run" << std::endl;
  else
    std::cout << m << " randomizations" << std::endl;
  run(n, m);
  return 0;
}