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