読者です 読者をやめる 読者になる 読者になる

CarrotBreeding (AOJ2375)

場合分けをするだけ.
とりあえずK点あれば基本K(K-1)/2本できる.a>=3点がcolinearならそっからa(a-1)/2-1本減る.(a=3から順に,2,5,9,14,20...)
大体K(K-1)/2がNを超えるようなKをとればできて(ただし余分が1か3だと無理),その時余分はだいたいKくらいなので,結構いい効率で詰め込みたい.a=6で14くらい減らせるのでこれを詰め込めばいい感じ.これでダメな奴はゴリ押し.これらの直線以外にどれも共線がないようにするには,y=10*x^2とかのまわりに点を並べればいい.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
void solve(int N){
	if(N==2){
		puts("-1");
		return;
	}
	if(N==7){
		puts("6");
		printf("1 0\n");
		printf("3 0\n");
		printf("9 0\n");
		printf("2 1\n");
		printf("3 2\n");
		printf("0 3\n");
		return;
	}
	int K=0;
	while(K*(K-1)/2<N) K++;
	if(K*(K-1)/2-N==1||K*(K-1)/2-N==3) K++;
	int off=K*(K-1)/2-N;
	vector<int> vc;
	if(off==9) vc.pb(5);
	if(off==10) vc.pb(4),vc.pb(4);
	if(off==11) vc.pb(3),vc.pb(5);
	if(off==12) vc.pb(3),vc.pb(4),vc.pb(4);
	if(off==13) vc.pb(3),vc.pb(3),vc.pb(5);
	if(off==14) vc.pb(6);
	if(off==15) rep(j,3) vc.pb(4);
	if(off==16) vc.pb(3),vc.pb(6);
	if(off==17) vc.pb(3),vc.pb(4),vc.pb(4),vc.pb(4);
	if(vc.empty()){
		if(off%2) vc.pb(4),off-=5;
		rep(i,off/14) vc.pb(6);
		off%=14;
		rep(i,off/2) vc.pb(3);
	}
	int sum=0;
	for(int a:vc) sum+=a;
/*	show(N);
	printf("vc.size()=%d     ",vc.size());
	rep(i,vc.size()) cout<<vc[i]<<" , ";
	puts("");
	show(K);
	puts("");*/
	if(sum>K){
//		printf("N=%d   K=%d  off=%d\n",N,K,offc);
		cout<<K<<endl;
		if(off==6){
			puts("0 0");
			puts("0 1");
			puts("0 2");
			puts("1 0");
			puts("1 1");
			puts("2 0");
			if(N==22){
				puts("114 514");
				puts("810 893");
			}
		}
		if(off==8){
			puts("0 0");
			puts("0 1");
			puts("0 2");
			puts("1 0");
			puts("1 2");
			puts("2 0");
			puts("2 1");
			puts("2 2");
			if(N>=37){
				puts("114 514");
				puts("810 893");
			}
			if(N==47){
				puts("114514 364364");
			}
		}
		if(off==12){
			puts("0 0");
			puts("0 1");
			puts("0 2");
			puts("0 3");
			puts("1 0");
			puts("2 0");
			puts("3 0");
			puts("2 1");
			puts("114 514");
			puts("810 893");
		}
		return;
	}
	cout<<K<<endl;
	rep(i,K-sum) vc.pb(1);
	int x=0;
	for(int a:vc){
		rep(i,a) printf("%d %d\n",x,x*x*10+i);
		x++;
	}
}
int main(){
	int N;
	cin>>N;
	solve(N);
}