//
// ex03.c：「アルゴリズムとデータ構造」第3回課題のソースコード例
//
// 作成者：井上 康介
// Ver.2：Oct. 15, 2011
//
// 概要：与えられた数の点から3点を選んで作れる3角形のうち，最大の
// 　　　面積を有する3角形を構成する頂点の番号とその面積を表示
//
// 使用方法：ex03.exe [arg1] [arg2] [arg3] [arg4]
//
// 　　　[arg1]：点の数 (正整数)
// 　　　[arg2]：乱数の種 (正整数)
// 　　　[arg3]：画面表示フラグ (ループで扱っている点の番号)
// 　　　[arg4]：保存フラグ (点座標および3角形頂点座標)
//
// 　　　※ コマンドライン引数はつけなくてもよい
//

#include <stdio.h>
#include <stdlib.h> // drand48()，atoi() のため
#include <math.h>   // fabs() のため

// 関数 SquareMeasure() のプロトタイプ宣言
double SquareMeasure(double *, double *, double *);


int main(int argc, char *argv[])
{
    int         i, j, k;       // 汎用変数
    int         num;           // 点の数
    double    **p;             // 点の座標の配列 (座標型)
    double      max;           // 「今のところの最大面積」
    int         points[3];     // 見つかった三角形の点番号
    double      s;             // 面積の一時保存先
    FILE       *fp;            // 出力用ファイルポインタ
    int         disp_flag = 0, // 表示するかどうかのフラグ
                save_flag = 0; // 保存するかどうかのフラグ


    //////////////////////////////////////////////// 点の数の設定
    // コマンドライン引数で与えられた場合
    if (argc > 1) {
        num = atoi(argv[1]); // 点の数を第1引数で設定

    }
    // 引数が与えられていないときはユーザ入力を促す
    else {
        printf("Input number of points: ");
        scanf("%d", &num);
    }
    // エラー処理
    if ((num < 3) || (num > 10000)) {
        fprintf(stderr, "Number of points is invalid.\n");
        exit(1);
    }


    //////////////////////////////////////////////// 乱数の種の設定
    if (argc > 2) {
        srand48(atoi(argv[2])); // 引数あり：乱数の種を第2引数で初期化
    }
    else {
        srand48(0);             // 引数なし：乱数の種を0で初期化
    }


    //////////////////////////////////////////////// フラグの設定
    if (argc > 3) disp_flag = atoi(argv[3]);
    if (argc > 4) save_flag = atoi(argv[4]);


    //////////////////////////////////////////////// 座標配列の動的確保
    // 与えられた点の数×2のサイズのdouble型二次元配列を作る

    // 最初にポインタの配列を動的確保
    if ((p = (double **)malloc(sizeof(double *) * num)) == NULL) {
        fprintf(stderr, "Cannot allocate memory for p[][].\n");
        exit(1);
    }

    // 実体の配列の確保（サイズはdouble型×点の数×2）
    if ((p[0] = (double *)malloc(sizeof(double) * num * 2)) == NULL) {
	fprintf(stderr, "Cannot allocate memory for p[][].\n");
	exit(1);
    }

    // ポインタ配列の中身を整備 (1つおきのポインタ値を入れる)
    for (i = 1; i < num; i++) 
	p[i] = p[0] + i * 2;


    //////////////////////////////////////////////// メイン部分

    // 点座標を乱数により設定 (座標値は [-5.0, 5.0) の範囲)
    for (i = 0; i < num; i++) {
        p[i][0] = 10.0 * drand48() - 5.0; // [0, 1) の一様乱数
        p[i][1] = 10.0 * drand48() - 5.0; // を10倍して5を引く
    }


    // 以下は saveフラグが立っているときだけ実行
    if (save_flag) {
        // 点座標出力ファイル output1.dat をオープン
        if ((fp = fopen("output1.dat", "w")) == NULL) {
            fprintf(stderr, "Cannot open file <output1.dat>\n");
            exit(1);
        }

        // 点座標をファイルへ書き込む
        for (i = 0; i < num; i++)
            fprintf(fp, "%f\t%f\n", p[i][0], p[i][1]);

        fclose(fp); // ファイルのクローズ
    }

    max = 0.0;  // max の初期化

    // メインの三重ループ
    for (i = 0; i < num - 2; i++)
        for (j = i + 1; j < num - 1; j++)
            for (k = j + 1; k < num; k++) {
                // dispフラグが立っていたら点番号を画面に表示
                if (disp_flag) printf("%3d%3d%3d\n", i, j, k);

                s = SquareMeasure(p[i],p[j],p[k]); // sに面積を代入

                // 更に大きい面積の三角形が見つかった場合
                if (s > max) {
                    max = s;       // max を更新
                    points[0] = i; // 点番号の保存
                    points[1] = j;
                    points[2] = k;
                }
            }

    // 結果の表示
    printf("Largest triangle: p[%d]-p[%d]-p[%d],\nSquareMeasure = %f\n\n",
           points[0], points[1], points[2], max);

    for (i = 0; i < 3; i++)
        printf("(%f, %f)\n", p[points[i]][0], p[points[i]][1]);
    

    //////////////////////////////////////////////// ファイル記録

    // 以下は saveフラグが立っているときだけ実行
    if (save_flag) {
        // 最大三角形保存用ファイル output2.dat のオープン
        if ((fp = fopen("output2.dat", "w")) == NULL) {
            fprintf(stderr, "Cannot open file <output2.dat>\n");
            exit(1);
        }

        // ファイルへの座標書き込み
        for (i = 0; i < 3; i++)
            fprintf(fp, "%f\t%f\n", p[points[i]][0], p[points[i]][1]);
        fprintf(fp, "%f\t%f\n", p[points[0]][0], p[points[0]][1]);

        // ファイルのクローズ
        fclose(fp);
    }


    //////////////////////////////////////////////// メモリ解放
    free(p[0]);
    free(p);

    return 0; // 正常終了時はプログラムを呼び出した相手に 0 を返す
}

// 三頂点の座標から三角形の面積を求める関数
double SquareMeasure(double *p0, double *p1, double *p2)
{
    double tmp;
    
    // 外積の z 成分の絶対値の0.5倍
    tmp = 0.5 * ((p1[0] - p0[0]) * (p2[1] - p0[1]) -
                 (p1[1] - p0[1]) * (p2[0] - p0[0]));

    // 負の値の時は逆転
    if (tmp < 0.0) tmp *= -1.0;

    return(tmp);
}