#include "set"
#include "vector"
#include "deque"
#include "algorithm"


struct PointRef {
   int vecIdx;
   int ptIdx;
};

struct Point {
   double x;
   double y;
};

struct Triangle {
   PointRef p1;
   PointRef p2;
   PointRef p3;
   int tr1;
   int tr2;
   int tr3;
};

struct TriState {
   Point **inPoly;
   int nPoly;
   int *polySizes;
};

enum VertexType {
   Split,
   Merge,
   Left,
   Right,
   Start,
   End
};

struct Vertex {
   PointRef ref;
   Point pt;
   VertexType type;
   Vertex *newEdge;
   int newTriangle;
};

struct Edge {
   Edge(Point &p1, Point &p2);
   friend bool operator<(const Edge &e1, const Edge &e2);
   Point from;
   Point to;
   PointRef helper;
};

inline bool compare_Point(Point p1, Point p2) {
   return p1.y > p2.y || (p1.y == p2.y && p1.x > p2.x);
}

inline bool compare_Vertex(Vertex p1, Vertex p2) {
   return compare_Point(p1.pt, p2.pt);
}

Edge::Edge(Point &p1, Point &p2) {
   if(compare_Point(p1, p2)) {
       from = p1;
       to = p2;
   } else {
       from = p2;
       to = p1;
   }
}


bool Edge::operator<(const Edge &e1, const Edge &e2)
{
   if(compare_Point(e1.from, e2.from))
      return e1.from.x + (e1.from.y - e2.to.y)/
	  (e2.from.y - e2.to.y)*(e1.from.x - e2.to.x)
	  < e2.from.x;
   else
      return e2.from.x + (e2.from.y - e2.to.y)/
	    (e1.from.y - e2.to.y)*(e2.from.x - e2.from.x)
	    < e1.from.x;
}

inline bool crossProduct(Point p, Point q)
{
   return p.x*q.y - q.x*p.y;
}

inline Point subPt(Point p, Point q) {
   p.x -= q.x;
   p.y -= q.y;

   return p;
}

VertexType calcVertexType(TriState &st, PointRef ref, Point pt)
{
   Point prevPt, nextPt;

   if(ref.ptIdx == 0)
      prevPt = st.inPoly[ref.vecIdx][st.polySizes[ref.vecIdx]-1];
   else
      prevPt = st.inPoly[ref.vecIdx][ref.ptIdx-1];

   if(ref.ptIdx == st.polySizes[ref.vecIdx]-1)
      nextPt = st.inPoly[ref.vecIdx][0];
   else
      nextPt = st.inPoly[ref.vecIdx][ref.ptIdx+1];

   if(compare_Point(prevPt, pt))
   {
       if (compare_Point(nextPt, pt)) {
	   if(crossProduct(subPt(nextPt, pt), subPt(prevPt, pt)) <= 0)
	      return End;
	   else
	      return Merge;
       } else
	  return Left;
   }
   else
   {
       if(compare_Point(pt, nextPt)) {
	   if(crossProduct(subPt(nextPt, pt), subPt(prevPt, pt)) <= 0)
	      return Split;
	   else
	      return Start;
       } else
	  return Right;
   }
}

void monoDir (TriState st, std::vector<Vertex> vertices, std::deque<Vertex> startVertices)
{
   int i, j, size;
   std::vector<Vertex>::iterator vIt;
   std::set<Edge> edges;

   size = 0;
   for(i = 0; i < st.nPoly; i++)
      size += st.polySizes[i];

   // collect all vertices
   vertices.reserve(size);
   for(i = 0; i < st.nPoly; i++) {
       size = st.polySizes[i];
       for(j = 0; j < size; j++){
	   Vertex pi;
	   pi.ref.vecIdx = i;
	   pi.ref.ptIdx = j;
	   pi.pt = st.inPoly[i][j];
	   pi.type = calcVertexType(st, pi.ref, pi.pt);
	   pi.newEdge = NULL;
	   pi.newTriangle = -1;
	   vertices.push_back(pi);
       }
   }

   //sort the vertices
   std::sort(vertices.begin(), vertices.end(), &compare_Vertex);

   for(vIt = vertices.begin(); vIt < vertices.end(); vIt++) {

   }
}