kmjp's blog

競技プログラミング参加記です

Codeforces #170 Div1. B. Set of Points

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

問題

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

解法

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

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

Mが5以上なら、外と内にM角形を作ればよい。N<2Mなら、外側の点を間引く。
Mが偶数だと4点並んじゃうので、(M+1)角形を作って外と内から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;
}
||

*まとめ
広告を非表示にする