Codeforces #170 Div1. B. Set of Points

CFで時々出る、解法の自由度が高い問題。
http://codeforces.com/contest/277/problem/B

問題

点の数Nと、M<=N<=2Mを満たす数Mが与えられる。
２次元座標上で、最も頂点数の多い凸図形がM角形となるようにN個の点を配置する。
なお、４点以上が一直線上に並んでは鳴らない。

解法

Nは2M以下なので、まず思いつくのは外側と内側に２重にM角形を作ること。
ただ、Mが偶数だと４点が一直線に並んでしまう。
自分の解法では内側を微妙に座標をずらしたりしたけどダメだった。

結局本番中に解けず、Editorialを見ながら解く。

Mが5以上なら、外と内にM角形を作ればよい。N<2Mなら、外側の点を間引く。
Mが偶数だと４点並んじゃうので、(M+1)角形を作って外と内から１点ずつ間引く。
M=3,4ではこれではダメなこともあるけど、そのパターンはわずかなので適当に決め撃ち。

int M,N;

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	M=GETi();
	
	if(M==3 && N==4) {
		_P("0 0\n");
		_P("5 0\n");
		_P("-5 -5\n");
		_P("-5 5\n");
		return;
	}
	if(M==3 && N>=5) {
		_P("-1\n");
		return;
	}
	
	if(M==4 && N>=7) {
		FOR(i,M) {
			x = 10000*cos(1+2*3.1415926535*i/M);
			y = 10000*sin(1+2*3.1415926535*i/M);
			_P("%d %d\n",x,y);
			if(M+i<N) {
				x = 1000000*cos(1+2*3.1415926535*i/(N-M));
				y = 1000000*sin(1+2*3.1415926535*i/(N-M));
				_P("%d %d\n",x,y);
			}
		}
	}
	else if(M%2) {
		FOR(i,M) {
			x = 10000*cos(2*3.1415926535*i/M);
			y = 10000*sin(2*3.1415926535*i/M);
			_P("%d %d\n",x,y);
			if(M+i<N) {
				x = 1000000*cos(2*3.1415926535*i/M);
				y = 1000000*sin(2*3.1415926535*i/M);
				_P("%d %d\n",x,y);
			}
		}
	}
	else {
		FOR(i,M) {
			x = 10000*cos(1+2*3.1415926535*i/(M+1));
			y = 10000*sin(1+2*3.1415926535*i/(M+1));
			_P("%d %d\n",x,y);
			if(M+i<N) {
				x = 1000000*cos(2*3.1415926535*(1+i)/(M+1));
				y = 1000000*sin(2*3.1415926535*(1+i)/(M+1));
				_P("%d %d\n",x,y);
			}
		}
	}
	
	
	return;
}
||

*まとめ