/*
* A189413.c
* Calculates the entries of Sloane's A189413 (counting convex quadrilaterals on an n X n grid)
*
* Created by Nathaniel Johnston (nathaniel@nathanieljohnston.com)
* April 25, 2011
*/

#include <math.h>
#include <stdio.h>

unsigned char pt[256][256];
FILE *file;

unsigned char isConvex (unsigned short a1, unsigned short a2, unsigned short b1, unsigned short b2, unsigned short c1, unsigned short c2, unsigned short d1, unsigned short d2)
{
    int s11,s12,s21,s22,s31,s32,s41,s42,t11,t12,t21,t22,t31,t32,t41,t42;
    s11 = b1-a1; s12 = b2-a2;
    s21 = d1-b1; s22 = d2-b2;
    s31 = c1-d1; s32 = c2-d2;
    s41 = a1-c1; s42 = a2-c2;
    t11 = b1-a1; t12 = b2-a2;
    t21 = c1-b1; t22 = c2-b2;
    t31 = d1-c1; t32 = d2-c2;
    t41 = a1-d1; t42 = a2-d2;

    if(((s11*s22 != s12*s21) && (s31*s22 != s32*s21) && (s31*s42 != s32*s41) && (s11*s42 != s12*s41) && fabs(2*M_PI - (acos((s11*s21 + s12*s22)/sqrt((s11*s11 + s12*s12)*(s21*s21 + s22*s22))) + acos((s21*s31 + s22*s32)/sqrt((s21*s21 + s22*s22)*(s31*s31 + s32*s32))) + acos((s31*s41 + s32*s42)/sqrt((s31*s31 + s32*s32)*(s41*s41 + s42*s42))) + acos((s41*s11 + s42*s12)/sqrt((s41*s41 + s42*s42)*(s11*s11 + s12*s12))))) < 0.0001) ||
    ((t11*t22 != t12*t21) && (t31*t22 != t32*t21) && (t31*t42 != t32*t41) && (t11*t42 != t12*t41) && fabs(2*M_PI - (acos((t11*t21 + t12*t22)/sqrt((t11*t11 + t12*t12)*(t21*t21 + t22*t22))) + acos((t21*t31 + t22*t32)/sqrt((t21*t21 + t22*t22)*(t31*t31 + t32*t32))) + acos((t31*t41 + t32*t42)/sqrt((t31*t31 + t32*t32)*(t41*t41 + t42*t42))) + acos((t41*t11 + t42*t12)/sqrt((t41*t41 + t42*t42)*(t11*t11 + t12*t12))))) < 0.0001)){
        return 1;}
    return 0;
}

int main ()
{
    unsigned short a, b, c, d, a1, a2, b1, b2, c1, c2, d1, d2, maxsz, sz, sz2;
    unsigned long long numPts;

    printf("This tool will calculate the entries of Sloane's A189413 (number of convex quadrilaterals on an n X n grid).\nPlease enter the number of terms to compute (an integer from 1 to 255): ");
    scanf("%d",&maxsz);
    numPts = 0;

    file = fopen("b189413.txt","w");
    fprintf(file,"1 0\n");
    fclose(file);
    printf("1 0\n");

    for(sz=2;sz<=maxsz;sz++){
        numPts = 0;
        sz2 = sz*sz;
        for(a=0;a<sz2;a++){
            a1 = a % sz; a2 = floor(a/sz);
            for(b=a+1;b<sz2;b++){
                b1 = b % sz; b2 = floor(b/sz);
                for(c=b+1;c<sz2;c++){
                    c1 = c % sz; c2 = floor(c/sz);
                    for(d=c+1;d<sz2;d++){
                        if(isConvex(a1, a2, b1, b2, c1, c2, d % sz, floor(d/sz))){
                            numPts++;
                        }
                    }
                }
            }
        }
        file = fopen("b189413.txt","a");
        fprintf(file,"%d %d\n",sz,numPts);
        fclose(file);
        printf("%d %d\n",sz,numPts);
    }

    printf("Done!");
    getchar();
    return 0;
}