// Qt C++ version

#include <limits>

#include <QPointF>
#include <QPolygonF>

bool doPolygonsIntersect(const QPolygonF& a, const QPolygonF& b)
{
  for(int polyi = 0; polyi < 2; ++polyi)
    {
      const QPolygonF& polygon = polyi == 0 ? a : b;

      for(int i1 = 0; i1 < polygon.size(); ++i1)
        {
          const int i2 = (i1 + 1) % polygon.size();

          const double normalx = polygon[i2].y() - polygon[i1].y();
          const double normaly = polygon[i2].x() - polygon[i1].x();

          double minA = std::numeric_limits<double>::max();
          double maxA = std::numeric_limits<double>::min();
          for(int ai = 0; ai < a.size(); ++ai)
            {
              const double projected = normalx * a[ai].x() +
                normaly * a[ai].y();
              if( projected < minA ) minA = projected;
              if( projected > maxA ) maxA = projected;
            }

          double minB = std::numeric_limits<double>::max();
          double maxB = std::numeric_limits<double>::min();
          for(int bi = 0; bi < b.size(); ++bi)
            {
              const double projected = normalx * b[bi].x() +
                normaly * b[bi].y();
              if( projected < minB ) minB = projected;
              if( projected > maxB ) maxB = projected;
            }

          if( maxA < minB || maxB < minA )
            return false;
        }
    }

  return true;
}

#include <iostream>

int main()
{
  QPolygonF a, b, c;
  a << QPointF(-5, 1) << QPointF(-3, 3) << QPointF(-1, 5)
    << QPointF( 1, 5) << QPointF( 3, 3) << QPointF( 5, 1)
    << QPointF( 5,-1) << QPointF( 3,-3) << QPointF( 1,-5)
    << QPointF(-1,-5) << QPointF(-3,-3) << QPointF(-5,-1);
  b << QPointF(-3, 0) << QPointF( 0, 3)
    << QPointF( 3, 0) << QPointF( 0,-3);
  c << QPointF( 4, 0) << QPointF( 7, 3)
    << QPointF(10, 0) << QPointF( 7,-3);

  std::cout
    << "Intersection(a,a) " << doPolygonsIntersect(a, a) << '\n'
    << "Intersection(a,b) " << doPolygonsIntersect(a, b) << '\n'
    << "Intersection(a,c) " << doPolygonsIntersect(a, c) << '\n'
    << "Intersection(b,a) " << doPolygonsIntersect(b, a) << '\n'
    << "Intersection(b,b) " << doPolygonsIntersect(b, b) << '\n'
    << "Intersection(b,c) " << doPolygonsIntersect(b, c) << '\n'
    << "Intersection(c,a) " << doPolygonsIntersect(c, a) << '\n'
    << "Intersection(c,b) " << doPolygonsIntersect(c, b) << '\n'
    << "Intersection(c,c) " << doPolygonsIntersect(c, c) << '\n';

  return 0;
}