さて、気づくか気づかないかで難易度が大幅に変わる問題。
http://codeforces.com/contest/268/problem/C
２次元座標のうち長方形の領域(0,0)-(W,H)が指定される。
その中で複数の格子点を選び、その格子点同士の距離が非整数になっているような格子点群のうち、数が最大のものを求めて点列の１例を返す問題。
ぱっと見、候補となる点が多くて簡単に解けないように見える。
だが考えてみると、点同士の距離が整数値を取れないとすると、同じx座標またはy座標の点は取れないことになる。
よって、取りうる数はmin(W,H)+1である。
次にそのような点列の１例を示す必要があるが、これは45度に１列に点を並べれば、それぞれの距離は√2の整数倍になるので、いずれも無理数になる。
(0,0)は使えないので、(0,H)から右下に点を延ばせばよい。
int N,M; int NG[10001]; void solve() { int f,r,i,j,k,l,x,y; ZERO(NG); GET2(&N,&M); _P("%d\n",min(N,M)+1); FOR(i,min(N,M)+1) { _P("%d %d\n",N-i,i); } return; }
まとめ
これまた、一瞬考えさせられるけど気が付くと瞬殺な問題。
こういう問題を考え付く頭がうらやましい。
