Language: C++

#include<complex>
#include<set>
#include<vector>
#include<iostream>
#include<fstream>
#include<stack>
#include<cmath>

#define SHAPE_A 1
#define SHAPE_B 2

#define FRONT 0x01
#define RIGHT 0x02
#define BACK 0x04
#define LEFT 0x08
#define OVER 0x10

#define sc second
#define fr first

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define CUR(i,n) (i%n)
#define NEXT(i,n) ((i+1)%n)
#define PREV(i,n) ((i-1+n)%n)

using namespace std;

typedef double elem;
typedef complex<elem> point, vec;
typedef pair<point, point> line, hline, seg, pp;

const elem eps = 1.0e-4;
const elem infty = 1e40;
const elem pi = acos(-1.0);
point base(0,0);

// oÍ
ostream &operator<<(ostream &os, const pair<point,point> &p){
  os << p.fr << "-" << p.sc;
  return os;
}

// lZ
inline elem sq(elem a){ return a*a; }
inline elem cq(elem a){ return a*a*a; }

// pxÏ·
elem rad(elem deg){ return (deg/180)*pi; }
elem deg(elem rad){ return (rad*180)/pi; }

// ®¬_Ìô¢AÈÇ
bool eq(elem a, elem b){ return abs(a-b) < eps; }
bool lt(elem a, elem b){ return !eq(a,b) && a < b; }
bool leq(elem a, elem b){ return eq(a,b) || a < b; }
bool gt(elem a, elem b){ return !eq(a,b) && a > b; }
bool geq(elem a, elem b){ return eq(a,b) || a > b; }
bool ltz(elem a){ return lt( a, 0 ); }
bool gtz(elem a){ return gt( a, 0 ); }
bool eqv(vec a, vec b){ return eq( abs(b-a),0); }
bool is_zv(vec v){ return eq(abs(v),0); }
elem emax(elem a, elem b){ return gt(a,b)?a:b; }
elem emin(elem a, elem b){ return lt(a,b)?a:b; }

bool lesspoint(const point &a, const point &b){
  return !eq( a.real(), b.real() ) ? lt( a.real(), b.real() ) : lt( a.imag(), b.imag() );
}

// _Iy[^
bool far(point a, point b){ return gtz( abs(b-a) ); }
bool near(point a, point b){ return leq( abs(b-a), 0 ); }
elem dot(vec a, vec b){ return (a.real() * b.real() + a.imag() * b.imag() ); }
elem cross(vec a, vec b){ return ( a.real() * b.imag() - a.imag() * b.real() ); }

// a©çbÜÅvñèÌpxAàpA]ñ]
elem varg(vec a, vec b){
  elem ret=arg(a)-arg(b);
  if(lt(ret,0))ret+=2*pi;
  if(gt(ret,2*pi))ret-=2*pi;
  if(eq(ret,2*pi))ret=0;
  return ret;
}
elem arg(vec a, vec b){ return acos( dot(a,b) / ( abs(a) * abs(b) ) ); }
point rot(point p, elem theta){ return p * polar((elem)1.0, theta); }
point rotdeg(point p, elem deg){ return p * polar((elem)1.0, rad(deg)); }
point proj(line l, point p){
  elem t=dot(p-l.first,l.first-l.second)/abs(l.first-l.second);
  return l.first + t*(l.first-l.second);
}
point reflect(line l, point p){ return p+(elem)2.0*(proj(l,p)-p); }

// ñ_Ô£A¼üÆ_ÌÅZ£AüªÆ_ÌÅZ£
elem dist(point a, point b){ return abs(a-b); }
elem dist_l(line l, point x){ return abs(cross(l.sc-l.fr,x-l.fr)) / abs(l.sc-l.fr); }
elem dist_seg(seg s, point x)
{
  if( ltz( dot(s.sc-s.fr,x-s.fr) ) ) return abs(x-s.fr);
  if( ltz( dot(s.fr-s.sc,x-s.sc) ) ) return abs(x-s.sc);
  return dist_l(s,x);
}

// PÊxNgA@üxNgAPÊ@üxNg
vec uvec(vec a){ return a / abs(a); }
vec nmr(vec a){ return a * vec(0,-1); }
vec nml(vec a){ return a * vec(0,1); }
vec unmr(vec a){ return uvec( nmr(a) ); }
vec unml(vec a){ return uvec( nml(a) ); }

// ¼ðA½s»è
bool orth(point a1, point a2, point b1, point b2){ return eq( dot( a2 - a1, b2 - b1 ), 0 ); }
bool orth(vec v1, vec v2){ return eq( dot(v1, v2), 0 ); }
bool prll(point a1, point a2, point b1, point b2){ return eq( cross( a2 - a1, b2 - b1 ), 0 ); }
bool prll(vec v1, vec v2){ return eq( cross(v1, v2), 0 ); }

// CCW oXg¾ªA¸xÉæé
int ccw(point a, point b, point x){
  b -= a;
  x -= a;
  // if( is_zv(b) || is_zv( x ) ) return ERROR;
  if( gtz( cross(b,x) ) ) return LEFT;
  if( ltz( cross(b,x) ) ) return RIGHT;
  if( ltz( dot(b,x) ) ) return BACK;
  if( lt( abs(b), abs(x) ) ) return FRONT;
  return OVER;
}

// üªÌð·»è
bool intersectedSS(seg a, seg b)
{
  if( ccw(a.fr,a.sc,b.fr)&OVER || ccw(a.fr,a.sc,b.sc)&OVER ) return true;
  return
    ( ccw(a.fr,a.sc,b.fr) | ccw(a.fr,a.sc,b.sc) ) == (LEFT|RIGHT) &&
    ( ccw(b.fr,b.sc,a.fr) | ccw(b.fr,b.sc,a.sc) ) == (LEFT|RIGHT) ;
}
// ¼üÌð·»è
bool intersectedLL(line a, line b){ return !eq( cross(a.sc-a.fr,b.sc-b.fr), 0.0 ); }

// ð_vZ
point intersectionSS(seg a, seg b)
{
  elem d1 = dist_l(b,a.fr);
  elem d2 = dist_l(b,a.sc);
  return a.fr + ( d1 / (d1 + d2 ) ) * (a.sc-a.fr);
}
point intersectionLL(line a, line b)
{
  vec va = a.sc - a.fr;
  vec vb = b.sc - b.fr;
  return a.fr + va * ( cross(vb, b.fr - a.fr) / cross(vb,va) );
}

// üªð_êÅ
bool intersectionLL(line a, line b, point &ret){
  return intersectedLL( a, b ) ? ret = intersectionLL( a, b ), true : false;
}
bool intersectionLH(line a, hline b, point &ret){
  point tmp;
  return intersectionLL(a,b,tmp) ? ( ccw(b.fr,b.sc,tmp)&(OVER|FRONT) ? ret=tmp, true : false ) : false;
}
bool intersectionLS(line l, seg s, point &ret){
  point tmp;
  return intersectionLL(l,s,tmp) ? ( ccw(s.fr,s.sc,tmp)&OVER ? ret=tmp, true : false ) : false;
}
bool intersectionHH(hline a, hline b, point &ret){
  point tmp;
  return intersectionLL(a,b,tmp) ? ( ccw(a.fr,a.sc,tmp)&(OVER|FRONT)&&ccw(b.fr,b.sc,tmp)&(OVER|FRONT) ? ret = tmp, true : false ) : false;
}
bool intersectionHS(hline a, seg s, point &ret){
  point tmp;
  return intersectionLS(a,s,tmp) ? ( ccw(a.fr,a.sc,tmp)&(OVER|FRONT) ? ret = tmp, true : false ) : false;
}
bool intersectionSS(seg a, seg b, point &ret){
  return intersectedSS(a,b) ? ret = intersectionSS(a,b), true : false;
}

// P½p`Ìàï»è(«EüÜÞ,¸_Æ¯¶ÊuÉ^¦çê½êoXgÈ»èÍoÈ¢)
bool inSimple(point x, const vector<point> &p)
{
  elem rad = 0;
  int n = p.size();
  for(int i = 0; i < n; ++i){
    int sign = 1;
    int cw = ccw(x,p[i],p[(i+1)%n]);
    int cw2 = ccw( p[i],p[(i+1)%n],x);
    if( near( x,p[i] ) ) return true;
    if( cw2 == OVER ) return true;
    if( cw & OVER ) continue;
    if( cw & RIGHT ) sign = -1;
    rad +=  sign * arg( vec(p[i]-x), vec(p[(i+1)%n]-x) );
  }
  return eq( rad, 2*pi );
}

// P½p`Ìàï»è(«EüÜÜÈ¢)
bool insideSimple(point x, const vector<point> &p)
{
  elem rad = 0;
  int n = p.size();
  for(int i = 0; i < n; ++i){
    int sign = 1;
    int cw = ccw(x,p[i],p[(i+1)%n]);
    int cw2 = ccw( p[i],p[(i+1)%n],x);
    if( near( x,p[i] ) ) return false;
    if( cw2 == OVER ) return false;
    if( cw & OVER ) continue;
    if( cw & RIGHT ) sign = -1;
    rad +=  sign * arg( vec(p[i]-x), vec(p[(i+1)%n]-x) );
  }
  return eq( rad, 2*pi );
}

static const elem shapeAdiag_l = 2. * cos(rad(18.0));
//*sqrt(1-(2.*(1.-cos(rad(36.0)))/4.));
static const elem shapeBdiag_l = 2. * cos(rad(36.0));
// sqrt(1-(2.*(1.-cos(rad(72.0)))/4.));
static const elem shapeBdiag_s = 2. * sin(rad(36.0));
// sqrt(1-(2.*(1.-cos(rad(144.0)))/4.));
static const elem shapeAdiag_s = 2. * sin(rad(18.0));
//sqrt(1-(2.*(1.-cos(rad(108.0)))/4.));

inline elem polArg(const vector<point> &vp, int i, int n){
  vec a(vp[PREV(i,n)]-vp[CUR(i,n)]);
  vec b(vp[NEXT(i,n)]-vp[CUR(i,n)]);
  return varg(a,b);
}

elem minArg(const vector<point> &vp){
  elem ret = infty;
  int n = vp.size();
  for(int i = 0; i < n; ++i){
    // cout << "VERTEX " << i << " : arg = " <<  polArg(vp,i,n) << endl;
    ret = min( ret, polArg( vp, i, n ) );
  }
  return ret;
}

bool lineWrapping(line a, line b){ // whether a wraps b
  if( leq( abs(b.sc-b.fr), abs(a.sc-a.fr) ) ){
    if( ccw( a.fr, a.sc, b.fr ) == OVER && ccw(a.fr, a.sc, b.sc ) == OVER ) return true;
  }
  return false;
}

class Point{
public:
  point p;
  Point():p(0.0,0.0){}
  Point(point p):p(p){}
  bool operator<(const Point &t)const{
    return !eq( p.real(), t.p.real() ) ? lt( p.real(), t.p.real() ) : lt( p.imag(), t.p.imag() );
  }
};

bool embed_slave(elem minarg, int i, const vector<point> &vp, int &chooseShape, point &prev, point &diag, point &next){
  int n = vp.size();
  chooseShape = SHAPE_A;
  vec va(vp[PREV(i,n)]-vp[CUR(i,n)]);
  vec vb(vp[NEXT(i,n)]-vp[CUR(i,n)]);
  vec vc;
  
  va = uvec( va );
  vb = uvec( vb );

  if( eq( minarg, rad(36.0) ) ){ vc = shapeAdiag_l * uvec( (va+vb)/(elem)2. );
  }else if( eq( minarg, rad(72.0) ) ){ chooseShape = SHAPE_B,  vc = shapeBdiag_l * uvec( (va+vb)/(elem)2. );
  }else if( eq( minarg, rad(108.0) ) ){ chooseShape = SHAPE_B,  vc = shapeBdiag_s * uvec( (va+vb)/(elem)2. );
  }else if( eq( minarg, rad(144.0) ) ){ vc = shapeAdiag_s * uvec( (va+vb)/(elem)2. );
  }else{ return false; }
  
  prev = vp[CUR(i,n)]+va;
  diag = vp[CUR(i,n)]+vc;
  next = vp[CUR(i,n)]+vb;
  return true;
}

void incIt(vector<point>::iterator &it, vector<point> &v, int n){
  assert(v.size()>1);
  if(it==v.end())it=v.begin();
  while(n>0){
    it++;if(it==v.end())it=v.begin();--n;
  }
}
void decIt(vector<point>::iterator &it, vector<point> &v, int n){
  assert(v.size()>1);
  while(n>0){
    if(it==v.begin())it=v.end();--it;--n;
  }
  if(it==v.end())--it;
}

bool embed(elem minarg, const vector<point> &vp, vector<point> &next,
	   int &nShapeA, int &nShapeB){
  int n = vp.size();
  bool allskip = false;

  //cout << "MINARG : " << minarg << endl;
  
  /* PÉ}`ð}üÅ«éê */
  vector<point> tmp;
  for(int i = 0; i < n; ++i){
    if( eq( minarg, polArg( vp, i, n ) ) && !allskip ){
      int chooseShape;
      point pprev, pdiag, pnext;
      
      if( !embed_slave( minarg, i, vp, chooseShape, pprev, pdiag, pnext ) ) return false;

      if( insideSimple( pdiag, vp ) && inSimple( pprev, vp ) && inSimple( pnext, vp ) ){
	//cout << " ADD : " << i << endl;
	tmp.push_back( pprev ); tmp.push_back( pdiag ); tmp.push_back( pnext );
	chooseShape == SHAPE_A ? ++nShapeA : ++nShapeB;
	allskip=true;
      }else{
	tmp.push_back( vp[i] );
      }
    }else{
      tmp.push_back( vp[i] );
    }
  }

  /* PÉ}`ð}üÅ«È¢êiO`ªå«­Ïíéj */
  if( !allskip ){
    int insertion_point = -1;
    int max_linewrap = 0;
    int chooseShape;
    point pprev, pdiag, pnext;
    set<Point> vis;

    for(int i = 0; i < n; ++i){
      vis.insert( Point( vp[i] ) );
      if( eq( minarg, polArg( vp, i, n ) ) && !allskip ){
	int nWrap = 0;

	if( !embed_slave( minarg, i, vp, chooseShape, pprev, pdiag, pnext ) ) return false;	

	line L[4];
	L[0]=line(vp[CUR(i,n)],pprev);
	L[1]=line(vp[CUR(i,n)],pnext);
	L[2]=line(pdiag,pprev);
	L[3]=line(pdiag,pnext);

	if( !inSimple(pprev,vp)||!inSimple(pnext,vp)||!inSimple(pdiag,vp) )continue;

	for(int k = 0; k < 4; ++k){
	  for(int j = 0; j < n; ++j){
	    line l(vp[CUR(j,n)],vp[NEXT(j,n)]);
	    if( lineWrapping( l, L[k] ) ){
	      ++nWrap;
	      break;
	    }
	  }
	}

	if( nWrap > max_linewrap ){
	  insertion_point = i;
	  max_linewrap = nWrap;
	}
      }
    }
    
    if( insertion_point < 0 ) return false;
    
    embed_slave( minarg, insertion_point, vp, chooseShape, pprev, pdiag, pnext );
    // cout << " WRAP : " << max_linewrap << endl;
    if ( max_linewrap <= 2 ){
      tmp.erase( tmp.begin() + insertion_point );
      tmp.insert( tmp.begin() + insertion_point, pnext );
      tmp.insert( tmp.begin() + insertion_point, pdiag );
      tmp.insert( tmp.begin() + insertion_point, pprev );
    }else{
      bool front=false;
      int cnt = 0;
      n=tmp.size();
      for(int j = insertion_point; cnt < 2; ++j,++cnt){
	//cout << "DEBUG : " << tmp[CUR(j,n)] << ' ' << tmp[NEXT(j,n)] << ' ' << pdiag << endl;
	if( ccw(tmp[CUR(j,n)], tmp[NEXT(j,n)], pdiag ) == OVER ){
	  front = true;
	  break;
	}
      }
      //cout << insertion_point << " : " << tmp[insertion_point] << endl;
      if( front ){
	//cout << "FRONT" << endl;
	vector<point>::iterator its = tmp.begin()+insertion_point;
	incIt(its,tmp,2); its = tmp.insert( its, pdiag );
	decIt(its,tmp,1); its = tmp.erase( its );
	decIt(its,tmp,1); its = tmp.erase( its );
	tmp.insert( its, pprev );
      }else{
	//cout << "BACK" << endl;
	vector<point>::iterator its = tmp.begin()+insertion_point;
	decIt(its,tmp,1); its = tmp.insert( its, pdiag );
	incIt(its,tmp,1); its = tmp.erase( its );
	incIt(its,tmp,1); its = tmp.insert( its, pnext );
	//cout << *its << endl;
	++its;
	decIt(its,tmp,2);
	// cout << *its << endl;
	its = tmp.erase( its );
      }
    }
    chooseShape == SHAPE_A ? ++nShapeA : ++nShapeB;
  }


  /* ®« */
  set<Point> vis;
  n = tmp.size();
  for(int i = 0; i < n; ++i){    
    if( vis.find( Point(tmp[CUR(i,n)]) ) == vis.end() ){
      vis.insert( Point(tmp[CUR(i,n)]) );
      next.push_back( tmp[CUR(i,n)] );
    }
  }

  n = next.size();
  for(int i = 0; i < n; ++i){
    elem polarg = polArg(next,i,n);
    if( eq( polarg , 0.0 ) || eq( polarg, 2*pi ) ){
      next.erase( next.begin() + i );
      --n;
      --i;
      if( n < 3 ) break;
    }
  }

  n = next.size();
  if( n >= 3 ){
    for(int i = 0; i < n; ++i){
      int cw = ccw( next[CUR(i,n)], next[NEXT(i,n)], next[NEXT(i+1,n)] );
      if( cw == FRONT ){
	next.erase( next.begin() + NEXT(i,n) );
	--n;
	--i;if(i<0)i=n-1;
      }else if( cw == OVER ){
	next.erase( next.begin() + NEXT(i+1,n) );
	--n;
	--i;if(i<0)i=n-1;
      }
      if(n<3)break;
    }
  }
  
  return true;
}

int main(){
  //  ofstream ofs("visual.txt");

  while(true){
    int n;
    bool ans = true;
    int nShapeA=0;
    int nShapeB=0;
    vector<point> vp;
    vector<point> tmp;

    cin >> n;
    if( cin.eof() )break;
    for(int i=0;i<n;++i){double x,y;cin>>x>>y;vp.push_back(point(x,y));}

    elem scale = 1.0;
    elem offset = 0;
    n = vp.size();

    /*
    for(int i = 0; i < n; ++i){
      ofs << "line(" << vp[CUR(i,n)].real() << ',' << vp[CUR(i,n)].imag() <<
	  ',' << vp[NEXT(i,n)].real() << ',' << vp[NEXT(i,n)].imag() << ");" << endl;
    }
    ofs << "//----------------------------------- " << endl;
    */

    while(true){
      if( !embed( minArg(vp), vp, tmp, nShapeA, nShapeB ) ){
	ans=false;
	break;
      }
      vp = tmp;
      tmp.clear();
     
      /*
      cout << "NUMBER OF SHAPE : " << nShapeA << ' ' << nShapeB << endl;
      cout << "SIZE : " << vp.size() << endl;
      for(int i = 0; i < vp.size(); ++i){
	cout << vp[i] << ' ';
      }
      cout << "\n--------------------------------" << endl;
      */

      /* for visualizer */
      elem scale = 1.0;
      elem offset = 0;
      int n = vp.size();
      /*
      for(int i = 0; i < n; ++i){
	ofs << "line(" << vp[CUR(i,n)].real() << ',' << vp[CUR(i,n)].imag() <<
	  ',' << vp[NEXT(i,n)].real() << ',' << vp[NEXT(i,n)].imag() << ");" << endl;
      }
      ofs << "//----------------------------------- " << endl;
      */
      
      if( vp.size() <= 2 ) break;
    }
    if( ans )
      cout << nShapeA << ' ' << nShapeB << endl;
    else
      cout << -1 << ' ' << -1 << endl;

    //ofs << "// END OF DATASET " << endl; 
  }

  //ofs.close();

  return 0;
}

Compiler output:
a.cc: In function 'void incIt(std::vector<std::complex<double> >::iterator&, std::vector<std::complex<double> >&, int)':
a.cc:276:3: error: 'assert' was not declared in this scope
  276 |   assert(v.size()>1);
      |   ^~~~~~
a.cc:8:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
    7 | #include<cmath>
  +++ |+#include <cassert>
    8 | 
a.cc: In function 'void decIt(std::vector<std::complex<double> >::iterator&, std::vector<std::complex<double> >&, int)':
a.cc:283:3: error: 'assert' was not declared in this scope
  283 |   assert(v.size()>1);
      |   ^~~~~~
a.cc:283:3: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'