解説

この問題は得点についての二分探索を行うことで $O(log N)$ で解くことができます。

まず、$N$ 回の移動の軌跡で作れる多角形の面積の最小値は $\frac{N}{2}-1$ です。
($1$ 辺の長さが $1$ の正方形のブロックを $k$ $(<\frac{N}{2}-1)$ 個を繋げて、周の長さを $N$ 以上にすることはできないからです。)

また、$N$ 回の移動の途中で訪れた格子点の $x$ 座標の最大値が $X$ のときに、面積が最大となる多角形の $1$ つに、
原点を頂点の $1$ つとする、$x$ 座標に平行な辺の長さが $X$ 、周の長さが $N$ の長方形があります。
このとき、 $y$ 座標に平行な辺の長さは $\frac{N}{2}-X$ となります。
$X<\frac{N}{2}-X$ のとき、長方形を原点を中心に $90$ 度回転させると $x$ 座標の最大値を $\frac{N}{2}-X$ にできるため、
最適ではありません。以下では $\frac{N}{2}-X \leq X$ すなわち、$\frac{N}{4} \leq X$ の場合で考えます。

得点($x$ 座標の最大値)が $X$ となるように移動するとき、上記より多角形の面積の最小値は $\frac{N}{2}-1$、最大値は $X(\frac{N}{2}-X)$ となりますが、
実は、 $\frac{N}{2}-1$ 以上、 $X(\frac{N}{2}-X)$ 以下の任意の整数の面積の多角形を作ることができます。
具体的には、長方形をベースにして、そこから減らしたい面積の分だけ内側を通ればよいです。

以下の図のように、周の長さが $N$であり、 $x$ 座標の最大値が $X$ であるような多角形の面積は
$\frac{N}{2}-1$ 以上、 $X(\frac{N}{2}-X)$ 以下の任意の整数にすることができます。
(外枠の赤線が軌跡を表しています。)

つまり、この問題は 「$\frac{N}{2}-1 \leq M \leq X(\frac{N}{2}-X)$ であるような最大の $X$ を求めよ」 と言い換えることができます。

「$M \leq X(\frac{N}{2}-X)$ である最大の $X$」は、$\frac{N}{4} \leq X$ の範囲において $f(X)=X(\frac{N}{2}-X)$ が単調減少であるため、
二分探索を用いて求めることができます。