#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
const int height=400;
const int width=400;//resolution
const int para_n[]={0,0,19,11,9,8,7,6};
const int para_s[]={1,2,4,8,16,32,64,128};
char* tested;
char signs[8];
double R;
int N;
typedef struct complex_num{double r;double i;}cpln;
cpln z;
const cpln one={1,0};
const cpln zero={0,0};
inline double ab(cpln c){return c.r*c.r+c.i*c.i;}//absolute value
inline cpln ad(cpln c,double x){c.r+=x;return c;}//adding real number
inline cpln adc(cpln c,cpln d){c.r+=d.r;c.i+=d.i;return c;}//cplx addition
inline cpln subc(cpln c,cpln d){c.r-=d.r;c.i-=d.i;return c;}
inline cpln mt(cpln c,cpln d){cpln r={c.r*d.r-c.i*d.i,c.r*d.i+c.i*d.r};return r;}//multiplication
inline cpln inv(cpln c){double u=c.r*c.r+c.i*c.i;cpln r={c.r/u,-c.i/u}; return r;}//1/z
inline cpln neg(cpln c){cpln r={-c.r,-c.i}; return r;}
inline cpln i2c(int i){cpln r={(double)i,0}; return r;}
int f(cpln c,cpln d,int i,long sym,int m){
if(i<N && ab(ad(c,-1))*height*width<ab(d))
return 1;
else if(i==0)
return 0;
cpln nc=mt(z,c);
cpln nd=adc(c,mt(z,d));
int t=sym%m;
if(signs[t]){nc=subc(i2c(t+1),nc);nd=neg(nd);}
else nc=subc(nc, i2c(t));
if(c.r>m/2)
{
for(int j=m-1;j>-1;j--)
if(f(nc,nd,i-1,sym*m+j,m))return 1;
}
else{
for(int j=0;j<m;j++)
if(f(nc,nd,i-1,sym*m+j,m))return 1;
}
return 0;
}
int chk(double x,double y, int m){
z.r=x;
z.i=y;
if(x*x+y*y>1||(m+1)*(m+1)*(x*x+y*y)<1)return 0;
if(f(one,zero,N,m-1,m))
return 1;
return 0;
}
int main()
{ long time=clock();
char* data=(char*)malloc(width*height);//pixels of the graph we are drawing
for(int i=0;i<width*height;i++)data[i]=0;
//check Gora's condition
for(int m=2;m<4;m++){
for(int s=0;s<para_s[m];s++){
printf("m=%d, s=%d\n",m,s);
long time2=clock();
N=para_n[m];
int s1=s;
for(int i=0;i<m;i++){signs[i]=s1%2;s1/=2;}
//find roots
for(int i=0;i<width;i++){
if(i%20==0)printf("%d\n",i);
for(int j=0;j<height;j++)
if(data[i+width*j]);
else if(j>height-j)data[i+width*j]=data[i+width*(height-j)];
else data[i+width*j]=m*chk(((double)i)*2/width-1,((double)j)*2/height-1, m);
}
free(tested);
printf("%ld\n",clock()-time2);
}
}
//output
int datas[]={0,255,210,170,130,90,50};
FILE* out=fopen("out.pgm","wb");
fprintf(out, "P2\n%d %d\n255\n",width, height);
for(int i=0;i<width*height;i++){
fprintf(out,"%d",datas[data[i]]);
if(i==width*height-1); else if(i%64==63)fputc('\n',out);else fputc(' ',out);}
fputc('\n',out);
fclose(out);
printf("%ld\n",clock()-time);
}
