Problem: Example

Input

4


Output

4
0 0
1 0
2 0
1 1

Solution (in CPP):

Solution:
#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
int x[2100];
int y[2100];
set<pair<pair<int,int>,pair<long long,long long> > >S;
int gcd(int a,int b){
	while(a){
		b%=a;
		int c=a;a=b;b=c;
	}
	return b;
}
int ABS(int a){return max(a,-a);}
bool chk(int ax,int ay,int at){
	for(int j=0;j<at;j++){
		int vx=ax-x[j];
		int vy=ay-y[j];
		if(vx<0){
			vx=-vx;vy=-vy;
		}
		int g=gcd(vx,vy);
		g=ABS(g);
		vx/=g;vy/=g;
		int fx=ax;
		int fy=ay;
		if(vx!=0){
			int div=fx/vx;
			if(S.count(make_pair(make_pair(vx,vy),make_pair(fx%vx,(long long)fy-(long long)div*vy))))return false;
		}else if(S.count(make_pair(make_pair(vx,vy),make_pair(fx,0))))return false;
	}
	return true;
}

int main(){
	int a;scanf("%d",&a);
	if(a==1){
		printf("2\n0 0\n0 1\n");return 0;
	}
	if(a==2){
		printf("-1\n");return 0;
	}
	if(a==7){
		printf("6\n0 0\n12 0\n6 3\n4 4\n8 4\n6 6\n");return 0;
	}
	if(a==9){
		printf("6\n0 0\n0 1\n0 2\n1 0\n1 1\n2 0\n");return 0;
	}
	if(a==20){
		printf("8\n0 0\n0 1\n0 2\n1 0\n1 2\n2 0\n2 1\n2 2\n");return 0;
	}
	int n=0;
	while(n*(n-1)/2<a){
		n++;
	}
	int rem=n*(n-1)/2-a;
	if(rem==1||rem==3){
		n++;
		rem=n*(n-1)/2-a;
	}
	int A=0;
	int B=0;
	int C=0;
	for(int i=0;i*3<=n;i++){
		for(int j=0;i*3+j*4<=n;j++){
			int t=rem-i*2-j*5;
			if(t<0)continue;
			if(t%9)continue;
			t/=9;
			if(i*3+j*4+t*5>n)continue;
			A=i;B=j;C=t;
		}
	}
	int D=n-A*3-B*4-C*5;
	int at=0;
	while(C){
		C--;
		while(1){
			int tx=rand()%960000000;
			int ty=rand()%960000000;
			int dx=rand()%10000000;
			int dy=rand()%10000000;
			bool ok=true;
			for(int i=0;i<5;i++){
				if(!chk(tx+dx*i,ty+dy*i,at)){ok=false;break;}
			}
			if(ok){
				for(int i=0;i<5;i++){
					x[at]=tx+dx*i;
					y[at]=ty+dy*i;
					for(int j=0;j<at;j++){
						int vx=x[at]-x[j];
						int vy=y[at]-y[j];
						if(vx<0){
							vx=-vx;vy=-vy;
						}
						int g=gcd(vx,vy);
						g=ABS(g);
						vx/=g;vy/=g;
						int fx=x[at];
						int fy=y[at];
						if(vx!=0){
							int div=fx/vx;
							S.insert(make_pair(make_pair(vx,vy),make_pair(fx%vx,(long long)fy-(long long)div*vy)));
						}else S.insert(make_pair(make_pair(vx,vy),make_pair(fx,0)));
					}
					at++;
				}
				break;
			}
		}
	}
	while(B){
		B--;
		while(1){
			int tx=rand()%960000000;
			int ty=rand()%960000000;
			int dx=rand()%10000000;
			int dy=rand()%10000000;
			bool ok=true;
			for(int i=0;i<4;i++){
				if(!chk(tx+dx*i,ty+dy*i,at)){ok=false;break;}
			}
			if(ok){
				for(int i=0;i<4;i++){
					x[at]=tx+dx*i;
					y[at]=ty+dy*i;
					for(int j=0;j<at;j++){
						int vx=x[at]-x[j];
						int vy=y[at]-y[j];
						if(vx<0){
							vx=-vx;vy=-vy;
						}
						int g=gcd(vx,vy);
						g=ABS(g);
						vx/=g;vy/=g;
						int fx=x[at];
						int fy=y[at];
						if(vx!=0){
							int div=fx/vx;
							S.insert(make_pair(make_pair(vx,vy),make_pair(fx%vx,(long long)fy-(long long)div*vy)));
						}else S.insert(make_pair(make_pair(vx,vy),make_pair(fx,0)));
					}
					at++;
				}
				break;
			}
		}
	}
	while(A){
		A--;
		while(1){
			int tx=rand()%960000000;
			int ty=rand()%960000000;
			int dx=rand()%10000000;
			int dy=rand()%10000000;
			bool ok=true;
			for(int i=0;i<3;i++){
				if(!chk(tx+dx*i,ty+dy*i,at)){ok=false;break;}
			}
			if(ok){
				for(int i=0;i<3;i++){
					x[at]=tx+dx*i;
					y[at]=ty+dy*i;
					for(int j=0;j<at;j++){
						int vx=x[at]-x[j];
						int vy=y[at]-y[j];
						if(vx<0){
							vx=-vx;vy=-vy;
						}
						int g=gcd(vx,vy);
						g=ABS(g);
						vx/=g;vy/=g;
						int fx=x[at];
						int fy=y[at];
						if(vx!=0){
							int div=fx/vx;
							S.insert(make_pair(make_pair(vx,vy),make_pair(fx%vx,(long long)fy-(long long)div*vy)));
						}else S.insert(make_pair(make_pair(vx,vy),make_pair(fx,0)));
					}
					at++;
				}
				break;
			}
		}
	}
	while(D){
		D--;
		while(1){
			int tx=rand()%960000000;
			int ty=rand()%960000000;
			int dx=rand()%10000000;
			int dy=rand()%10000000;
			bool ok=true;
			for(int i=0;i<1;i++){
				if(!chk(tx+dx*i,ty+dy*i,at)){ok=false;break;}
			}
			if(ok){
				for(int i=0;i<1;i++){
					x[at]=tx+dx*i;
					y[at]=ty+dy*i;
					for(int j=0;j<at;j++){
						int vx=x[at]-x[j];
						int vy=y[at]-y[j];
						if(vx<0){
							vx=-vx;vy=-vy;
						}
						int g=gcd(vx,vy);
						g=ABS(g);
						vx/=g;vy/=g;
						int fx=x[at];
						int fy=y[at];
						if(vx!=0){
							int div=fx/vx;
							S.insert(make_pair(make_pair(vx,vy),make_pair(fx%vx,(long long)fy-(long long)div*vy)));
						}else S.insert(make_pair(make_pair(vx,vy),make_pair(fx,0)));
					}
					at++;
				}
				break;
			}
		}
	}
	printf("%d\n",n);
	for(int i=0;i<n;i++)printf("%d %d\n",x[i],y[i]);
}