/*
2003/06 正三角形はいくつ?
coded by Isaku WADA
 ┌─────────────────────────────┐
 │ Fig.3のように,正三角格子状に並 Fig.3 37個のドット配置│
 │んだ37個のドットがある。この中に,      ・        │
 │3つのドットを結んでできる正三角形       ・・    │
 │は何個あるだろうか。たとえばFig.4    ・・・・・・・ │
 │には,4種類の大きさの正三角形が15     ・・・・・・  │
 │個ある。                  ・・・・・  │
 │Fig.4 ドットの例             ・・・・・・  │
 │     ・               ・・・・・・・ │
 │     ・・                 ・・    │
 │    ・・・                 ・    │
 │    ・・・・                      │
 └─────────────────────────────┘
 ┌──────┐
 │解答:240│
 └──────┘
 ┌──────────────┬──────┬───────┐
 │コンパイラ         │実行時間  │ファイルサイズ│
 ├──────────────┼──────┼───────┤
 │Microsoft Visual C++ 6.0  │0.00001000秒│ 36864 byte │
 │Microsoft Visual C++ .NET  │0.00000953秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │0.00001344秒│ 54272 byte │
 │gcc-2.953(djgpp)      │0.00001099秒│ 109041 byte │
 │gcc-2.953(cygwin)      │0.00001110秒│ 19923 byte │
 │LSI C-86 Ver 3.30 試食版  │0.00005490秒│ 13944 byte │
 │Turbo C Ver 1.5(small model)│0.00004990秒│ 11420 byte │
 ├──────────────┼──────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP     │
 └──────────────┴──────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ 平面上の点について「高さが下の方が後ろ、同じ高さなら右の│
 │方が後ろ」という順序付けをします。プログラムは、配置を見な│
 │がら37個のドットに、この順序で座標値を設定してゆきます。│
 │原点は左上です。縮尺は、横方向では隣り合うドットの距離を2│
 │とします。縦方向では隣り合う行の距離を1とします。これから│
 │は、座標値のことをベクトルと呼びます。          │
 │ 探索は、まず、設定した37個のベクトルのうち、最後を除く│
 │36個から、2つのベクトルx(x1 x2)とy(y1 y2)を選びます。こ│
 │のとき、2重forループでyの順序がxよりも後になるように選び │
 │ます。次に、差のベクトルd(d1 d2)←y-xを求めます。そして、x│
 │を中心にyを60度回転させたベクトルz(z1 z2)を求めます。zの│
 │順序をyよりも後にするため、d1>d2なら右回り、-d1>=d2なら左 │
 │回りにします。右回りでも左回りでもない場合は、スキップしま│
 │す。zはAを回転行列とすると、z←x+Adにより求めることがで │
 │きます。右回転行列は                   │
 │                             │
 │ (  0.5 -1.5 )                      │
 │ (  0.5  0.5 )                      │
 │                             │
 │で、左回転行列は                     │
 │                             │
 │ (  0.5  1.5 )                      │
 │ ( -0.5  0.5 )                      │
 │                             │
 │です。                          │
 │ zはxとyとで正三角形を形成しています。そこで、zが盤の範囲│
 │に含まれ、そこにドットが配置されていれば数えます。xとyとz │
 │の順序は常に昇順なので、同じ正三角形を2度以上数えることは│
 │ありません。                       │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 最初は、3重forループで3点を選び、3辺が等しいかどうか │
 │で数えていました。このとき、現在の2倍以上の計算時間がかか│
 │っていました。改良の鍵となる、60度回転を浮動小数点数なし│
 │で実現する方法を導くのに苦労しました。          │
 └─────────────────────────────┘*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
const char*Shape[]=
{"      ・      ",
 "     ・・     ",
 "・・・・・・・",
 " ・・・・・・ ",
 "  ・・・・・  ",
 " ・・・・・・ ",
 "・・・・・・・",
 "     ・・     ",
 "      ・      "};

#define MAX_DOT 37 /* 必ずドット数以上にすること */
#define LINES (sizeof Shape/sizeof*Shape)

/*┌──────────┐
 │グローバル変数の宣言│
 └──────────┘*/
int NumOfDot; /* ドットの数 */
int Count;    /* 正三角形の数 */
int Width;    /* 盤の幅 */

/*┌─────────────────────────┐
 │正三角形を表示する。xが-1ならフラッシュする    │
 │x,yと(z1 z2)は●を表示。それ以外の点は・を表示する│
 └─────────────────────────┘*/
void Print(int x,int y,int z1,int z2)
{
    int i,j,k; static int col; static char buf[LINES][80];

    if (x!=-1) {  /* 盤の状態をバッファに溜め込む */
        for (k=i=0;i<LINES;i++) {
            if (col) strcat(buf[i],"  ");
            for (j=0;j<Width;j++) {
                if (Shape[i][j]==' ') strcat(buf[i]," ");
                else {
                    if (k==x||k==y||(i==z2&&j==z1))
                         strcat(buf[i],"●");
                    else strcat(buf[i],"・");
                    j++; k++;
                }
            }
        }
        col++;
    }
    /* バッファに溜まった内容をフラッシュする */
    if ((x==-1&&col)||col==80/(Width+2)) {
        for (i=0;i<LINES;i++)
        { printf("%s\n",buf[i]); buf[i][0]=0; }
        col=0; printf("\n");
    }
}

/*┌───────────────────────┐
 │正三角形の数を求める。引数が0以外なら表示する│
 └───────────────────────┘*/
void Solve(int prn)
{
    static int vec1[MAX_DOT],vec2[MAX_DOT];
    int x,y, x1,x2, d1,d2, z1,z2;

    Width=(int)strlen(Shape[0]); Count=NumOfDot=0;
    /* 37個のベクトルを設定する */
    for (x2=0;x2<LINES;x2++) for (x1=0;x1<Width;x1++)
     if (Shape[x2][x1]!=' ')
     { vec1[NumOfDot]=x1; vec2[NumOfDot]=x2; NumOfDot++; x1++; }

    /* 正三角形の探索 */
    for (x=0;x<NumOfDot-2;x++) { /* 中心となるベクトルxを選ぶ */
        x1=vec1[x]; x2=vec2[x];

        for (y=x+1;y<NumOfDot-1;y++) { /* 回転するベクトルyを選ぶ */

            d2=vec2[y]-x2; d1=vec1[y]-x1;  /* 差のベクトルd */

            /* xを中心にyを60度回転させたzを求める */
            if (d1>d2)   { z1=x1+(d1-3*d2)/2; z2=x2+(d1+d2)/2; }
            else
            if (-d1>=d2) { z1=x1+(d1+3*d2)/2; z2=x2+(-d1+d2)/2; }
            else continue;

            if (z1>=0&&z1<Width&&z2<LINES) /* 盤の上にある */
             if (Shape[z2][z1]!=' ') {     /* ドットの上にある */
                 if (prn) Print(x,y,z1,z2);
                 Count++;
             }
        }
    }
}


/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌────────────────────┐
 │メイン・ルーチン            │
 │引数を指定しないと正三角形を書き出す  │
 │引数に繰り返し数を指定すると書き出さない│
 └────────────────────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); long i,num; int prn=(argc==1);

    if (argc==2) num=atol(argv[1]); else num=1;
    for (i=0;i<num;i++) Solve(prn);
    if (prn) Print(-1,0,0,0); /* バッファをフラッシュする */
    printf("ドットの数 : %d   正三角形の数 : %d   ",NumOfDot,Count);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}