WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #170 Div2 D "Set of Points"

問題

整数N,Mが与えられる。
どの頂点も凸になっているM角形を作れるように、
上手い事N個の点を配置しなさい。
どの頂点も凸になっているMより多い頂点を持つ
多角形が作れちゃだめ。

また、点を配置する時は任意の3つの点が一直線に並んではならないし、
絶対値で10^8を超えてはならない。
そのような点が配置できなければ-1を出力しなさい。

例)
4 3
点を結んで凸の多角形を作る時、
最大で頂点が3になるように、
4つの点を配置する。
(0,0) (1,0) (0,1) (1,1)のように配置しちゃうと、
凸の四角形が作れちゃうからダメ
サンプルにあるように
(0,0) (3,0) (0,3) (1,1)と配置すると、
凸の多角形は三角形までしか作れないからOK

制約

3 <= M <= 100
M <= N <= 2M

ACしてるコードを見たところ・・・

まずM個の点を全て凸になるように配置していかなくてはならない。
y = x^2 (x>=0)のような線上に点を配置していけば、
その点を結んだ時に、でこぼこせずに、ぼこぼこした線になるし、
どの3点も一直線上に並ばない。
とりあえずM個の点はy=x^2 (x>=0)...(A)の線上に配置していく。


残りのR個の点 (制約よりR<=M)はy=-x^2-1 (x>=0)...(B)の線上に配置するようにする。
こうすることで、(A)と(B)の点を両方使った時に出来る凸の多角形は
四角形までに制限できるようになる。
五角形以上の多角形を作ると必ず凹の部分が出来てしまう。


このようにしてM個の点を(A)上に、R個の点を(B)上に配置する事により、
(A)だけ使った凸の多角形はM角形まで
(B)だけ使った凸の多角形はR角形まで
(A)と(B)を使うと凸の多角形は四角形までとなり、
M >= 4ならば点を配置できるようになる
M = 3でもN = 4の時は
R = 1となるため、
(A)と(B)を使っても三角形までしか作れなくなり配置できる。


ただし、このままだと(A)と(B)の3つの点が一直線上に並ぶ危険性がでてくる。
しかし(A)と(B)をy軸方向で十分に距離をとればよい。
例えばy=x^2 + 10^6...(A) y=-x^2 - 10^6...(B)とする。
こうすると、(A)の任意の2点を結んでできる直線は
y<0の時は必ずx<0になり(B)の点を通る事はない。(B)も同じ。



こんなん無理・・・

ソースコード
int main() {

	int N, M;
	cin >> N >> M;

	if( M == 3 ){
		if( N == 5 || N == 6 ){
			cout << -1 << endl;
			return 0;
		}
	}

	for( int i = 0; i < M; i++ ){
		printf( "%d %d\n", i, static_cast<int>(1e6)+i*i );
	}
	int r = N - M;
	for( int i = 0; i < r; i++ ){
		printf( "%d %d\n", i,static_cast<int>(-1e6)-i*i );
	}
        return 0;
}