/* This program is described in the last two paragraphs of the appendix in our paper and was used to compute the numbers that appear in Table 8 and the numbers for even sided ngons that appear in Table 7. To compile this program name it ngon.c and use an ANSI C compiler such as the GNU C compiler. On most unix platforms you should type gcc ngon.c -lm to compile the program, and then type a.out to run it. */ #include #include #include #define pi 3.1415926535897932384626433 /* global variables */ double pts_x[300000]; /*stores the x coordinate of the intersection points*/ double pts_y[300000]; /*stores the y coordinate of the intersection points*/ int lines[300000][4]; /* stores the indices of the four vertices that determine an intersection point */ int sporadic[66][6]; /* stores the 65 sporadic solutions to (2) */ int N; /* the number of sides of the ngon */ void sort(int l, int r); /*quicksort on the x coordinates*/ void sort2(int l, int r); /*quicksort on the y coordinates*/ void swap(int m, int n); /*swap used by both quicksorts*/ /* the following 4 subroutines are used to check that two close points are really the same. To be absolutely sure that a pair of close points p_A and p_B are actually the same, it checks that for the two pairs of diagonals (l_1,l_2) and (l_3,l_4) determining p_A and p_B, respectively, the triples l_1,l_2,l_3 and l_1,l_2,l_4 each divide the circle into arcs of lengths consistent with Theorem 4. */ void check_kosher(int A, int B); int check_trivial(int a,int b,int c,int d,int e,int f); int check_sporadic(int a,int b,int c,int d,int e,int f); int check_family(int a,int b,int c,int d,int e,int f); int gcd(int a, int b); /* finds the gcd of two integers */ main() { int i,j,k,l,U; /* variables used in looping and */ double q,s,t,u,v,z,A,B,C,D; /* in computations */ double x[1000],y[1000]; /* stores the x and y coordinates of the vertices of the ngon */ int M; /* used to break up the slice of the pie into 20 smaller pieces */ int count; /* keeps track of no of intrsctn pts in the smaller piece */ int total; /* counts the number of intersection points found. Used to check that focusing on a slightly smaller region didn't cause any intersection points to be missed */ double slope_1, slope_2; /* determines the region of the ngon that is to be examined */ int a[8]; /* a[k] is equal to a_k(N)/N that appears in our paper */ char c; int table; /* used to determine which table to produce. The user the output. */ int lower,upper,increment; /* used to determine which ngons to examine */ do{ printf("\nEnter 8 to produce the data in Table 8. Enter 7 to produce\n"); printf("the data (for even sided ngons) in Table 7:\n"); c=getchar(); table=c-'7'; }while(table!=0&&table!=1); if(table==1){ lower=6; upper=420; increment=6; printf("\n\nThe first eight columns correspond to the columns in\n"); printf("Table 8. The last number is used to check that no intersection\n"); printf("points were omitted and should equal zero.\n\n"); } else{ lower=4; upper=30; increment=2; printf("\n\nThe first eight columns correspond to the first 8 columns\n"); printf("in Table 7. The last number is used to check that no\n"); printf("intersection points were omitted and should equal zero.\n\n"); } /* the 65 sporadic solutions to (2) */ sporadic[1][0]=3; sporadic[1][1]=4; sporadic[1][2]=9; sporadic[1][3]=4; sporadic[1][4]=5; sporadic[1][5]=5; sporadic[2][0]=2; sporadic[2][1]=5; sporadic[2][2]=8; sporadic[2][3]=3; sporadic[2][4]=3; sporadic[2][5]=9; sporadic[3][0]=2; sporadic[3][1]=4; sporadic[3][2]=11; sporadic[3][3]=3; sporadic[3][4]=5; sporadic[3][5]=5; sporadic[4][0]=2; sporadic[4][1]=2; sporadic[4][2]=14; sporadic[4][3]=2; sporadic[4][4]=3; sporadic[4][5]=7; sporadic[5][0]=1; sporadic[5][1]=7; sporadic[5][2]=9; sporadic[5][3]=2; sporadic[5][4]=4; sporadic[5][5]=7; sporadic[6][0]=1; sporadic[6][1]=7; sporadic[6][2]=8; sporadic[6][3]=2; sporadic[6][4]=3; sporadic[6][5]=9; sporadic[7][0]=1; sporadic[7][1]=5; sporadic[7][2]=13; sporadic[7][3]=3; sporadic[7][4]=4; sporadic[7][5]=4; sporadic[8][0]=1; sporadic[8][1]=5; sporadic[8][2]=11; sporadic[8][3]=2; sporadic[8][4]=3; sporadic[8][5]=8; sporadic[9][0]=1; sporadic[9][1]=3; sporadic[9][2]=14; sporadic[9][3]=2; sporadic[9][4]=2; sporadic[9][5]=8; sporadic[10][0]=1; sporadic[10][1]=3; sporadic[10][2]=13; sporadic[10][3]=1; sporadic[10][4]=4; sporadic[10][5]=8; sporadic[11][0]=1; sporadic[11][1]=2; sporadic[11][2]=19; sporadic[11][3]=2; sporadic[11][4]=3; sporadic[11][5]=3; sporadic[12][0]=1; sporadic[12][1]=2; sporadic[12][2]=16; sporadic[12][3]=1; sporadic[12][4]=3; sporadic[12][5]=7; sporadic[13][0]=1; sporadic[13][1]=1; sporadic[13][2]=21; sporadic[13][3]=1; sporadic[13][4]=2; sporadic[13][5]=4; sporadic[14][0]=3; sporadic[14][1]=5; sporadic[14][2]=15; sporadic[14][3]=4; sporadic[14][4]=5; sporadic[14][5]=10; sporadic[15][0]=2; sporadic[15][1]=8; sporadic[15][2]=13; sporadic[15][3]=3; sporadic[15][4]=7; sporadic[15][5]=9; sporadic[16][0]=1; sporadic[16][1]=9; sporadic[16][2]=15; sporadic[16][3]=2; sporadic[16][4]=7; sporadic[16][5]=8; sporadic[17][0]=1; sporadic[17][1]=7; sporadic[17][2]=19; sporadic[17][3]=3; sporadic[17][4]=4; sporadic[17][5]=8; sporadic[18][0]=1; sporadic[18][1]=7; sporadic[18][2]=13; sporadic[18][3]=2; sporadic[18][4]=3; sporadic[18][5]=16; sporadic[19][0]=1; sporadic[19][1]=2; sporadic[19][2]=26; sporadic[19][3]=1; sporadic[19][4]=3; sporadic[19][5]=9; sporadic[20][0]=5; sporadic[20][1]=10; sporadic[20][2]=17; sporadic[20][3]=8; sporadic[20][4]=9; sporadic[20][5]=11; sporadic[21][0]=5; sporadic[21][1]=8; sporadic[21][2]=19; sporadic[21][3]=6; sporadic[21][4]=9; sporadic[21][5]=13; sporadic[22][0]=4; sporadic[22][1]=11; sporadic[22][2]=13; sporadic[22][3]=5; sporadic[22][4]=6; sporadic[22][5]=21; sporadic[23][0]=3; sporadic[23][1]=11; sporadic[23][2]=18; sporadic[23][3]=5; sporadic[23][4]=7; sporadic[23][5]=16; sporadic[24][0]=3; sporadic[24][1]=6; sporadic[24][2]=23; sporadic[24][3]=4; sporadic[24][4]=5; sporadic[24][5]=19; sporadic[25][0]=3; sporadic[25][1]=5; sporadic[25][2]=29; sporadic[25][3]=4; sporadic[25][4]=6; sporadic[25][5]=13; sporadic[26][0]=3; sporadic[26][1]=5; sporadic[26][2]=27; sporadic[26][3]=4; sporadic[26][4]=5; sporadic[26][5]=16; sporadic[27][0]=3; sporadic[27][1]=5; sporadic[27][2]=25; sporadic[27][3]=3; sporadic[27][4]=6; sporadic[27][5]=18; sporadic[28][0]=2; sporadic[28][1]=7; sporadic[28][2]=19; sporadic[28][3]=3; sporadic[28][4]=4; sporadic[28][5]=25; sporadic[29][0]=2; sporadic[29][1]=5; sporadic[29][2]=35; sporadic[29][3]=4; sporadic[29][4]=6; sporadic[29][5]=8; sporadic[30][0]=2; sporadic[30][1]=3; sporadic[30][2]=33; sporadic[30][3]=2; sporadic[30][4]=4; sporadic[30][5]=16; sporadic[31][0]=1; sporadic[31][1]=18; sporadic[31][2]=21; sporadic[31][3]=5; sporadic[31][4]=7; sporadic[31][5]=8; sporadic[32][0]=1; sporadic[32][1]=16; sporadic[32][2]=23; sporadic[32][3]=5; sporadic[32][4]=6; sporadic[32][5]=9; sporadic[33][0]=1; sporadic[33][1]=16; sporadic[33][2]=18; sporadic[33][3]=3; sporadic[33][4]=5; sporadic[33][5]=17; sporadic[34][0]=1; sporadic[34][1]=14; sporadic[34][2]=25; sporadic[34][3]=4; sporadic[34][4]=7; sporadic[34][5]=9; sporadic[35][0]=1; sporadic[35][1]=13; sporadic[35][2]=27; sporadic[35][3]=5; sporadic[35][4]=6; sporadic[35][5]=8; sporadic[36][0]=1; sporadic[36][1]=13; sporadic[36][2]=25; sporadic[36][3]=3; sporadic[36][4]=8; sporadic[36][5]=10; sporadic[37][0]=1; sporadic[37][1]=13; sporadic[37][2]=22; sporadic[37][3]=3; sporadic[37][4]=5; sporadic[37][5]=16; sporadic[38][0]=1; sporadic[38][1]=10; sporadic[38][2]=31; sporadic[38][3]=4; sporadic[38][4]=6; sporadic[38][5]=8; sporadic[39][0]=1; sporadic[39][1]=10; sporadic[39][2]=25; sporadic[39][3]=3; sporadic[39][4]=4; sporadic[39][5]=17; sporadic[40][0]=1; sporadic[40][1]=8; sporadic[40][2]=27; sporadic[40][3]=2; sporadic[40][4]=5; sporadic[40][5]=17; sporadic[41][0]=1; sporadic[41][1]=6; sporadic[41][2]=31; sporadic[41][3]=2; sporadic[41][4]=4; sporadic[41][5]=16; sporadic[42][0]=7; sporadic[42][1]=18; sporadic[42][2]=19; sporadic[42][3]=11; sporadic[42][4]=13; sporadic[42][5]=16; sporadic[43][0]=6; sporadic[43][1]=11; sporadic[43][2]=23; sporadic[43][3]=7; sporadic[43][4]=8; sporadic[43][5]=29; sporadic[44][0]=4; sporadic[44][1]=13; sporadic[44][2]=23; sporadic[44][3]=6; sporadic[44][4]=7; sporadic[44][5]=31; sporadic[45][0]=2; sporadic[45][1]=7; sporadic[45][2]=49; sporadic[45][3]=4; sporadic[45][4]=6; sporadic[45][5]=16; sporadic[46][0]=1; sporadic[46][1]=25; sporadic[46][2]=30; sporadic[46][3]=5; sporadic[46][4]=7; sporadic[46][5]=16; sporadic[47][0]=1; sporadic[47][1]=20; sporadic[47][2]=35; sporadic[47][3]=5; sporadic[47][4]=6; sporadic[47][5]=17; sporadic[48][0]=1; sporadic[48][1]=18; sporadic[48][2]=37; sporadic[48][3]=4; sporadic[48][4]=7; sporadic[48][5]=17; sporadic[49][0]=1; sporadic[49][1]=14; sporadic[49][2]=43; sporadic[49][3]=4; sporadic[49][4]=6; sporadic[49][5]=16; sporadic[50][0]=5; sporadic[50][1]=13; sporadic[50][2]=35; sporadic[50][3]=11; sporadic[50][4]=12; sporadic[50][5]=14; sporadic[51][0]=2; sporadic[51][1]=19; sporadic[51][2]=32; sporadic[51][3]=5; sporadic[51][4]=9; sporadic[51][5]=23; sporadic[52][0]=1; sporadic[52][1]=23; sporadic[52][2]=31; sporadic[52][3]=4; sporadic[52][4]=6; sporadic[52][5]=25; sporadic[53][0]=1; sporadic[53][1]=17; sporadic[53][2]=47; sporadic[53][3]=5; sporadic[53][4]=8; sporadic[53][5]=12; sporadic[54][0]=13; sporadic[54][1]=18; sporadic[54][2]=31; sporadic[54][3]=16; sporadic[54][4]=19; sporadic[54][5]=23; sporadic[55][0]=10; sporadic[55][1]=19; sporadic[55][2]=29; sporadic[55][3]=12; sporadic[55][4]=13; sporadic[55][5]=37; sporadic[56][0]=6; sporadic[56][1]=23; sporadic[56][2]=29; sporadic[56][3]=8; sporadic[56][4]=13; sporadic[56][5]=41; sporadic[57][0]=2; sporadic[57][1]=13; sporadic[57][2]=73; sporadic[57][3]=6; sporadic[57][4]=10; sporadic[57][5]=16; sporadic[58][0]=1; sporadic[58][1]=42; sporadic[58][2]=43; sporadic[58][3]=7; sporadic[58][4]=11; sporadic[58][5]=16; sporadic[59][0]=1; sporadic[59][1]=36; sporadic[59][2]=49; sporadic[59][3]=7; sporadic[59][4]=10; sporadic[59][5]=17; sporadic[60][0]=1; sporadic[60][1]=32; sporadic[60][2]=53; sporadic[60][3]=6; sporadic[60][4]=11; sporadic[60][5]=17; sporadic[61][0]=1; sporadic[61][1]=26; sporadic[61][2]=61; sporadic[61][3]=6; sporadic[61][4]=10; sporadic[61][5]=16; sporadic[62][0]=14; sporadic[62][1]=41; sporadic[62][2]=48; sporadic[62][3]=15; sporadic[62][4]=31; sporadic[62][5]=61; sporadic[63][0]=13; sporadic[63][1]=21; sporadic[63][2]=83; sporadic[63][3]=15; sporadic[63][4]=24; sporadic[63][5]=54; sporadic[64][0]=6; sporadic[64][1]=28; sporadic[64][2]=97; sporadic[64][3]=15; sporadic[64][4]=17; sporadic[64][5]=47; sporadic[65][0]=1; sporadic[65][1]=45; sporadic[65][2]=121; sporadic[65][3]=11; sporadic[65][4]=14; sporadic[65][5]=18; /* look at ngons with N sides */ for(N=lower;N<=upper;N=N+increment){ total=0; for(k=0;k<=N-1;k++){ x[k]=cos(2*k*pi/N); y[k]=sin(2*k*pi/N); } for(k=2;k<=7;k++)a[k]=0; /* focus attention on 2*pi/N radians of the ngon. Further, to cut down on the number of intersection points, break this region into 20 smaller pieces. The .00000000001 (in 'slope_1 =...' and 'slope_2 =...') is to avoid counting points twice, though we might potentially miss some intersection points. However, by comparing the total number of intersection points found with the theoretical prediction we can make sure that we haven't missed any. The .00000123 is to avoid the potential problem caused by the many intersection points that lie on the lines with angles 0 and 2*pi/N */ /* break the region into 20 smaller pieces*/ for (M=1;M<=20;M++){ count=0; slope_1 = tan((M-1)*2*pi/(N*20)+.00000123+.00000000001); slope_2 = tan(M*2*pi/(N*20)+.00000123-.00000000001); /* finds intersection points in a region slightly larger than one slice of the pie. Even though this part could be made more efficient, most of the computation is spent later on sorting the points, so we don't mind */ U=N/2; for(j=2;j<=U-1;j++) for(l=j+U;l!=1;l=(l+1)%N) for(i=1;iq)B=(q*A*A-sqrt(A*A+1-q*q*A*A))/(A*A+1); else B=(q*A*A+sqrt(A*A+1-q*q*A*A))/(A*A+1); C=A*(B-q); } s=atan(C/B); if(s>0)s=s+pi; else s=2*pi+s; s=s*N/(2*pi); if(l==0)s=N-1; k=(int)s; do{ /* compute the intersection point (u,v) of the two diagonals determined by the four vertices with indices i,j,k,l */ A=x[j]-x[l]; B=x[k]-x[i]; C=y[j]-y[l]; D=y[k]-y[i]; t=(D*(x[k]-x[l])-B*(y[k]-y[l]))/(A*D-B*C); u=x[l]+t*(x[j]-x[l]); v=y[l]+t*(y[j]-y[l]); /* make sure not to include the origin. Then if the point (u,v) lies within the region determined by the lines with slopes slope_1 and slope_2 (and within the first quadrant of the x-y plane) append (u,v) to the list of intersection points. Also record the four vertices v_i,v_j,v_k,v_l tha gave rise to (u,v) */ if(u>.000001||u<-.00001) /* makes sure not to include the origin */ if(v/u>slope_1&&v/u<=slope_2){ count++; if(count>299999) printf("WARNING- we've exceeded 299999\n"); else{ lines[count][0]=i; lines[count][1]=j; lines[count][2]=k; lines[count][3]=l; pts_x[count]=u; pts_y[count]=v; total++; } } k=k-1; }while(v1){ sort(1,count); /* sort the int. pts. according to their x cood.*/ i=1; do{ j=i; /* look for clumps of points with close x coordinates */ do{ j=j+1; }while(pts_x[j]-pts_x[i]<.0000000000001&& pts_x[i]-pts_x[j]<.0000000000001&&j<=count); j=j-1; if (j>i) sort2(i,j); /* sort the clumps according to their y coordinate */ i=j+1; }while(i1){ /* verify that the points are indeed the same. If not, a warning message is printed (see check_kosher).*/ for(k=1;k<=l-1;k++) check_kosher(i,i+k); z=(1+sqrt(1+8*l))/2+.000000001; k=(int)z; /* k equals the # of diagonals that meet at a common point */ a[k]++; } else a[2]++; i=j+1; }while(i<=count); } /*else if(count>1) */ } /* for M */ /* print out all the info. The first eight numbers correspond to the columns in Table 8/first 8 column in Table 7. The last number is used to check that no intersection points were omitted and should equal zero */ if(table==1){ printf("%d: %8d %6d %4d %4d %3d %3d %10d %10d\n", N,a[2],a[3],a[4],a[5],a[6],a[7], a[2]+a[3]+a[4]+a[5]+a[6]+a[7], total-((N-1)*(N-2)*(N-3)-3*N+6)/24); } else{ printf("%d: %8d %6d %4d %4d %3d %3d %10d %10d\n", N,N*a[2],N*a[3],N*a[4],N*a[5],N*a[6],N*a[7], N*(a[2]+a[3]+a[4]+a[5]+a[6]+a[7])+1, total-((N-1)*(N-2)*(N-3)-3*N+6)/24); } } /* for N */ } void sort(int l, int r) { int i,last; if(l>=r) return; swap(l,(l+r)/2); last=l; for(i=l+1;i<=r;i++) if(pts_x[i]=r) return; swap(l,(l+r)/2); last=l; for(i=l+1;i<=r;i++) if(pts_y[i]i&&Ic) {tmp=a;a=c;c=tmp;} if(a>e) {tmp=a;a=e;e=tmp;} if(c>e) {tmp=c;c=e;e=tmp;} if(b>d) {tmp=b;b=d;d=tmp;} if(b>f) {tmp=b;b=f;f=tmp;} if(d>f) {tmp=d;d=f;f=tmp;} kosher_1=check_trivial(a,b,c,d,e,f); if(kosher_1==1) kosher_1=check_family(a,b,c,d,e,f); if(kosher_1==1) kosher_1=check_sporadic(a,b,c,d,e,f); if(kosher_1==1)printf("ANOMALY %d %d %d %d %d %d\n",a,c,e,b,d,f); } if(J!=i&&J!=j){ if(Ji&&Jc) {tmp=a;a=c;c=tmp;} if(a>e) {tmp=a;a=e;e=tmp;} if(c>e) {tmp=c;c=e;e=tmp;} if(b>d) {tmp=b;b=d;d=tmp;} if(b>f) {tmp=b;b=f;f=tmp;} if(d>f) {tmp=d;d=f;f=tmp;} kosher_2=check_trivial(a,b,c,d,e,f); if(kosher_2==1) kosher_2=check_family(a,b,c,d,e,f); if(kosher_2==1) kosher_2=check_sporadic(a,b,c,d,e,f); if(kosher_2==1)printf("ANOMALY %d %d %d %d %d %d\n",a,c,e,b,d,f); } } int check_trivial(int a,int b,int c,int d,int e,int f) { if(a==b&&c==d&&e==f) return 0; else return 1; } int check_sporadic(int a,int b,int c,int d,int e,int f) { int i,val=1,g; g=gcd(a,b);g=gcd(g,c);g=gcd(g,d);g=gcd(g,e);g=gcd(g,f); a=a/g;b=b/g;c=c/g;d=d/g;e=e/g;f=f/g; i=1; do{ if(a==sporadic[i][0]&& c==sporadic[i][1]&& e==sporadic[i][2]&& b==sporadic[i][3]&& d==sporadic[i][4]&& f==sporadic[i][5]) val=0; if(b==sporadic[i][0]&& d==sporadic[i][1]&& f==sporadic[i][2]&& a==sporadic[i][3]&& c==sporadic[i][4]&& e==sporadic[i][5]) val=0; i++; }while(i<=65&&val==1); return val; } int check_family(int a,int b,int c,int d,int e,int f) { int A,B,C,D,E,F,tmp,max; double t,z; if(e>f) max=e; else max=f; /* check if in family 3 */ t=7./12-(max*1./N); /* since, in family 3, 7/12-t is the max value */ z=N*(7./12-t)+.000000001; E=(int)z; z=N*2*t+.000000001; C=(int)z; z=N*(1./12-t)+.000000001; A=(int)z; z=N*(2*t)+.000000001; F=(int)z; z=N*(1./6-2*t)+.000000001; D=(int)z; z=N*1./6+.000000001; B=(int)z; if(A>C) {tmp=A;A=C;C=tmp;} if(A>E) {tmp=A;A=E;E=tmp;} if(C>E) {tmp=C;C=E;E=tmp;} if(B>D) {tmp=B;B=D;D=tmp;} if(B>F) {tmp=B;B=F;F=tmp;} if(D>F) {tmp=D;D=F;F=tmp;} if((a==A&&b==B&&c==C&&d==D&&e==E&&f==F)|| (b==A&&d==C&&f==E&&a==B&&c==D&&e==F)) return 0; else{ /* check_1 if in family 2. There are two verifications for family 2 since the max can either be 1/6+t or 1/2-3t */ t=(max*1./N)-1./6; z=N*(1./6+t)+.000000001; E=(int)z; z=N*2*t+.000000001; C=(int)z; z=N*(1./6-t)+.000000001; A=(int)z; z=N*t+.000000001; F=(int)z; z=N*(1./2-3*t)+.000000001; D=(int)z; z=N*1./6+.000000001; B=(int)z; if(A>C){tmp=A;A=C;C=tmp;} if(A>E){tmp=A;A=E;E=tmp;} if(C>E){tmp=C;C=E;E=tmp;} if(B>D){tmp=B;B=D;D=tmp;} if(B>F){tmp=B;B=F;F=tmp;} if(D>F){tmp=D;D=F;F=tmp;} if((a==A&&b==B&&c==C&&d==D&&e==E&&f==F)|| (b==A&&d==C&&f==E&&a==B&&c==D&&e==F)) return 0; else{ /* check_2 if in family 2 */ t=(1./2-(max*1./N))/3; z=N*(1./2-3*t)+.000000001; E=(int)z; z=N*t+.000000001; C=(int)z; z=N*1./6+.000000001; A=(int)z; z=N*2*t+.000000001; F=(int)z; z=N*(1./6-t)+.000000001; D=(int)z; z=N*(1./6+t)+.000000001; B=(int)z; if(A>C){tmp=A;A=C;C=tmp;} if(A>E){tmp=A;A=E;E=tmp;} if(C>E){tmp=C;C=E;E=tmp;} if(B>D){tmp=B;B=D;D=tmp;} if(B>F){tmp=B;B=F;F=tmp;} if(D>F){tmp=D;D=F;F=tmp;} if((a==A&&b==B&&c==C&&d==D&&e==E&&f==F)|| (b==A&&d==C&&f==E&&a==B&&c==D&&e==F)) return 0; else{ /* check if in family 1 */ t=(max*1./N)-1./3; z=N*(1./3+t)+.000000001; E=(int)z; z=N*t+.000000001; C=(int)z; z=N*(1./6-t)+.000000001; A=(int)z; z=N*t+.000000001; F=(int)z; z=N*(1./3-2*t)+.000000001; D=(int)z; z=N*1./6+.000000001; B=(int)z; if(A>C){tmp=A;A=C;C=tmp;} if(A>E){tmp=A;A=E;E=tmp;} if(C>E){tmp=C;C=E;E=tmp;} if(B>D){tmp=B;B=D;D=tmp;} if(B>F){tmp=B;B=F;F=tmp;} if(D>F){tmp=D;D=F;F=tmp;} if((a==A&&b==B&&c==C&&d==D&&e==E&&f==F)|| (b==A&&d==C&&f==E&&a==B&&c==D&&e==F)) return 0; else{ /* check if in family 4 */ t=(max*1./N)-1./3; z=N*(1./3+t)+.000000001;E=(int)z; z=N*t+.000000001;C=(int)z; z=N*(1./3-4*t)+.000000001;A=(int) z; z=N*(3*t)+.000000001;F=(int)z; z=N*(1./6-2*t)+.000000001;D=(int)z; z=N*(1./6+t)+.000000001;B=(int)z; if(A>C){tmp=A;A=C;C=tmp;} if(A>E){tmp=A;A=E;E=tmp;} if(C>E){tmp=C;C=E;E=tmp;} if(B>D){tmp=B;B=D;D=tmp;} if(B>F){tmp=B;B=F;F=tmp;} if(D>F){tmp=D;D=F;F=tmp;} if((a==A&&b==B&&c==C&&d==D&&e==E&&f==F)|| (b==A&&d==C&&f==E&&a==B&&c==D&&e==F)) return 0; } } } } return 1; } int gcd(int a,int b) { int r; if(a>b) {r=a;a=b;b=r;} do{ r=(b%a);b=a;a=r; }while(r>0); return b; }