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); }