#include <iostream>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <math.h>

#define BE(v) v.begin(),v.end()

typedef pair<int,int> Tpoint;

typedef vector<Tpoint> Ttriangle;

int level;
int maxsize=1;

set <Ttriangle> triangles,newtriangles;

set <Tpoint> points,rpoints;

void view (Tpoint const point) {
cout << point.first << " " << point.second << "  "; 
} 

void view (Ttriangle const t) {
view(t[0]);
view(t[1]);
view(t[2]);
cout << "\n";
} 

int order(set<Tpoint> ps,Tpoint p) {
set<Tpoint>::iterator it=ps.find(p);
return distance(ps.begin(),it);
}

int intorder(set<int> ps,int p) {
set<int>::iterator it=ps.find(p);
return distance(ps.begin(),it);
}

void triangles2points(void) {
// cout << "triangles to points\n";
points.clear();
for (set<Ttriangle>::iterator it=triangles.begin();it!=triangles.end();it++) {
//  view(*it);
  for (int i=0;i<3;i++) {
    points.insert((*it)[i]);
  }
}
}

void triangles2matrix(void) {
vector <set<int> > mat(points.size());
vector <int> old2new(points.size()),new2old(points.size());
stringstream ss;

// cout << mat.size();
for (set<Ttriangle>::iterator it=triangles.begin();it!=triangles.end();it++) {
    int x,y,z;
    x=order(points,(*it)[0]);
    y=order(points,(*it)[1]);
    z=order(points,(*it)[2]);
    mat[x].insert(y);
    mat[x].insert(z);
    mat[y].insert(x);
    mat[y].insert(z);
    mat[z].insert(x);
    mat[z].insert(y);
}

// find new order
// first the interior
int ii=0;
int i;
for (i=0;i<points.size();i++) {
 if (mat[i].size()==6) {
   old2new[i]=ii;
   new2old[ii]=i;
   ii++;
 }
}
// then the boundary 
i=0;
for (i=0;i<points.size();i++) {
 if (mat[i].size()<6) {
   old2new[i]=ii;
   new2old[ii]=i;
   ii++;
 }
} 

// write out
ss.str("");
ss << "all.nbd.xy." << level << ".txt";
ofstream all(ss.str().c_str());
all.precision(20);

for (i=0;i<points.size();i++) {
  all << i+1 << "  ";
  for (set<int>::iterator jt=mat[new2old[i]].begin();jt!=mat[new2old[i]].end();jt++ ) {
    all << old2new[*jt]+1 << " ";
  }
  for (int d=0;d<6-mat[new2old[i]].size();d++) all << "0 ";
  set<Tpoint>::iterator it=points.begin();
  advance(it,new2old[i]);
  double  r= (*it).first;
  double  s= (*it).second;
  double m=maxsize;
  double rad=sqrt(3.0)*m/2*2/3;
//  cout << maxsize << " " << m << "\n";
  all << (r+s/2.0-m/2.0)/rad << " " << (sqrt(3.0)*s/2.0-sqrt(3.0)/2.0*m/3.0)/rad << "\n" ; 
}
all.close();
}


void viewpoints() {
for (set<Tpoint>::iterator it=points.begin();it!=points.end();it++) {
  view(*it);
  cout << "\n";
}
cout << "\n";
}


void shifttriangle(Ttriangle &t, int x, int y) {
t[0].first +=x;
t[0].second +=y;
t[1].first +=x;
t[1].second +=y;
t[2].first +=x;
t[2].second +=y;
}

void addlevel(Ttriangle triangle) {
Ttriangle ntriangle;
Tpoint nx,ny,nz,ntype;
int type=triangle[3].first;
// cout << type << "type\n";
// view(triangle);
Tpoint x=triangle[0];
Tpoint y=triangle[1];
Tpoint z=triangle[2];
int size=y.first-x.first;
int nsize=size/3;
// cout << nsize << "nsize\n";
if (type) {                         // type 1    
    ntriangle.clear();                   // type 1 (sits on corner)
  nx.first=x.first;               
  nx.second=x.second;
  ntriangle.push_back(nx);
  ny.first=x.first+nsize;
  ny.second=x.second;
  ntriangle.push_back(ny);
  nz.first=x.first+nsize;
  nz.second=x.second-nsize;
  ntriangle.push_back(nz);
  ntype=make_pair(1,0);             
  ntriangle.push_back(ntype);
//  view(ntriangle);
  newtriangles.insert(ntriangle);

  shifttriangle(ntriangle,nsize,0);
  newtriangles.insert(ntriangle);  
  
  shifttriangle(ntriangle,nsize,0);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,0,-nsize);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,0,-nsize);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,-nsize,nsize);
  newtriangles.insert(ntriangle);


  ntriangle.clear();                  // type 0
  nx.first=x.first+nsize;               
  nx.second=x.second;
  ntriangle.push_back(nx);
  ny.first=x.first+2*nsize;
  ny.second=x.second;
  ntriangle.push_back(ny);
  nz.first=x.first+nsize;
  nz.second=x.second+nsize;
  ntriangle.push_back(nz);
  ntype=make_pair(0,0);             
  ntriangle.push_back(ntype);
//  view(ntriangle);
  newtriangles.insert(ntriangle);

  shifttriangle(ntriangle,0,-nsize);
  newtriangles.insert(ntriangle);  
  
  shifttriangle(ntriangle,0,-nsize);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,nsize,0);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,0,nsize);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,nsize,-nsize);
  newtriangles.insert(ntriangle);
}
else {                            // type 0
  ntriangle.clear();                   // type 1 (sits on corner)
  nx.first=x.first+nsize;               
  nx.second=x.second;
  ntriangle.push_back(nx);
  ny.first=x.first+2*nsize;
  ny.second=x.second;
  ntriangle.push_back(ny);
  nz.first=x.first+2*nsize;
  nz.second=x.second-nsize;
  ntriangle.push_back(nz);
  ntype=make_pair(1,0);             
  ntriangle.push_back(ntype);
//  view(ntriangle);
  newtriangles.insert(ntriangle);

  shifttriangle(ntriangle,0,nsize);
  newtriangles.insert(ntriangle);  
  
  shifttriangle(ntriangle,0,nsize);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,-nsize,0);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,-nsize,0);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,nsize,-nsize);
  newtriangles.insert(ntriangle);


  ntriangle.clear();                  // type 0
  nx.first=x.first;               
  nx.second=x.second;
  ntriangle.push_back(nx);
  ny.first=x.first+nsize;
  ny.second=x.second;
  ntriangle.push_back(ny);
  nz.first=x.first;
  nz.second=x.second+nsize;
  ntriangle.push_back(nz);
  ntype=make_pair(0,0);             
  ntriangle.push_back(ntype);
//  view(ntriangle);
  newtriangles.insert(ntriangle);

  shifttriangle(ntriangle,0,nsize);
  newtriangles.insert(ntriangle);  
  
  shifttriangle(ntriangle,0,nsize);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,nsize,-nsize);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,0,-nsize);
  newtriangles.insert(ntriangle);
  
  shifttriangle(ntriangle,nsize,0);
  newtriangles.insert(ntriangle);
}
}

void addlevelall(void) {
// cout << "newlevel\n";
newtriangles.clear();
for_each(BE(triangles),addlevel);
triangles=newtriangles;
newtriangles.clear();
}

main() {
level=4;
for (int i=0;i<level;i++) maxsize *= 3;
// cout << maxsize;

//                             initial triangle
Tpoint point=make_pair(0,0);
//Tpoint point=make_pair(-1,2);
Ttriangle triangle;
triangle.push_back(point);
point=make_pair(maxsize,0);
//point=make_pair(2,2);
triangle.push_back(point);
point=make_pair(0,maxsize);
//point=make_pair(2,-1);
triangle.push_back(point);
point=make_pair(0,1);         // type 0 triangle (sits on a side)
triangle.push_back(point);

triangles.insert(triangle);

for (int ii=0;ii<level;ii++ ) addlevelall();

/*
  cout << "Level " << level;
  cout << "\nTriangles " << triangles.size();
  cout << "\nPoints " << points.size();
  cout << "\npoint  xcoord ycoord   connected_to_points\n";
*/

triangles2points();
triangles2matrix();


}