No one was able to solve it in the actual test. But I heard that one of the teachers gave the students a wonderful solution. P.S. $ \sqrt{2}n $ is very easy but making it slightly bigger is very hard. I think this problem is a little similar to LATTICE POINT PROBLEM.

@above It was actually Ju JungHoon who gave the solution during the lock-in

I know the solution he has but I heard that someone else gave them a wonderful solution.

Some double counting gives us the perimeter of $P$ is bigger than $\sqrt{\frac{65}{32}}(n-2)$, then we're done. Anyway, what's the known best constant as $\sqrt{2}+\epsilon$?

I got a PM request for the details, so here it is: Let $S$ be set of $n$ lattice points in a general position. Among them, let $x_0=\min x, x_1=\max x, y_0=\min y, y_1=\max y$ and $p_0=\min x+y, p_1=\max x+y, q_0=\min y-x, q_1=\max y-x$. Also define $\Delta x=x_1-x_0, \Delta y=y_1-y_0, \Delta p=p_1-p_0, \Delta q=q_1-q_0$, and $k=\frac{\min(\Delta p, \Delta q)}{4}$. So we get $p_0\leq x+y\leq p_1$, and $q_0\leq y-x\leq q_1$. Also define $\Delta X=\Delta x+\Delta y, \Delta P=\Delta p+\Delta q$. Now define eight regions: $$A_p^+: p_1-k<x+y\leq p_1, \;A_p^-: p_0\leq x+y<p_0+k$$$$A_q^+: q_1-k<y-x\leq q_1, \;A_q^-: q_0\leq y-x<q_0+k$$And $$B_y: \frac{p_0+q_0}{2}+k\leq y\leq \frac{p_1+q_1}{2}-k, \;B_x: \frac{p_0-q_1}{2}+k\leq x\leq \frac{p_1-q_0}{2}-k$$$$C_y: \frac{p_0+q_0+k}{2}\leq y\leq\frac{p_1+q_1-k}{2}, \;C_x: \frac{p_0-q_1+k}{2}\leq x\leq \frac{p_1-q_0-k}{2}$$First, I'll prove that $|S\cap A_p^+|+|S\cap A_p^-|+|S\cap A_q^+|+|S\cap A_q^-|+|S\cap B_y|+|S\cap B_x|+|S\cap C_y|+|S\cap C_x|\geq 4|S|$. It suffices to prove that these 8 region covers region $p_0\leq x+y\leq p_1$, $q_0\leq y-x\leq q_1$ at least four times. Case I: $(x,y)\in B_x\cap B_y$ Note that $B_x\subset C_x$ and $B_y\subset C_y$, hence it's counted at least four times: $B_x,B_y,C_x,C_y$. Case II: $(x,y)\not\in C_x\cap C_y$ Note that all the sets are symmetric wrt $x,y$ or $p,q$. So without loss of generality we only have to prove when $y>\frac{p_1+q_1-k}{2}$. First, $x\leq p_1-y<p_1-\frac{p_1+q_1-k}{2}\leq \frac{p_1-q_1}{2}+k=\frac{p_1-q_0}{2}-k+(2k-\frac{q_1-q_0}{2})\leq \frac{p_1-q_0}{2}-k$, and similarly $x> \frac{p_0-q_1}{2}+k$. Therefore $(x,y)\in B_x$, and since $B_x\subset C_x$, it is also in $C_x$. Note that $x+y=2y-(y-x)>(p_1+q_1-k)-q_1=p_1-k$, and similarly $y-x>q_1-k$. Therefore $(x,y)\in A_p^+, A_q^+$, as desired. Case III: $(x,y)\in C_x\cap C_y$, $(x,y)\not\in B_x\cap B_y$ Without loss of generality, we can assume that $\frac{p_1+q_1}{2}-k<y\leq \frac{p_1+q_1-k}{2}$. Similarly, $x\leq p_1-y<p_1-\frac{p_1+q_1}{2}+k\leq \frac{p_1-q_0}{2}-k$ and $x>\frac{p_0-q_1}{2}+k$. Therefore $(x,y)\in B_x$. Note that $(x+y)+(y-x)>(p_1-k)+(q_1-k)$ implies $x+y> p_1-k$ or $y-x>q_1$ holds, therefore $(x,y)\in A_p^+$ or $A_q^+$. Therefore $(x,y)\in C_x,C_y,B_x$ and $A_p^+$ or $A_q^+$, as desired. So summing up, we get $|S\cap A_p^+|+|S\cap A_p^-|+|S\cap A_q^+|+|S\cap A_q^-|+|S\cap B_y|+|S\cap B_x|+|S\cap C_y|+|S\cap C_x|\geq 4|S|$. Note that since $S$ is in a general poition, any line contains at most 2 points. Especially, each lines in form of $x=a, y=b, x+y=c,x-y=d$ contains at most 2 points. Now we get some inequalities: - Partitioning $S$ into $x=i$, $x_0\leq i \leq x_1$, we get $n\leq 2(\Delta x+1)$. Similarly, $n\leq 2(\Delta y +1)$. - Partitioning $S$ into $x+y=i$, $p_0\leq i\leq p_1$, we get $n\leq 2(\Delta p+1)$. Similarly, $n\leq 2(\Delta q+1)$. Now we get $n\leq \Delta x+\Delta y+2=\Delta X+2$, and $n\leq 2+2\min(\Delta p, \Delta q)=8k+2$. Also, applying same logic to the sets we defined before, - Considering $x+y$'s, $A_p^+$ contains at most $2(p_1-(p_1-k))=2k$ elements of $S$, and similar for $A_p^-, A_q^+, A_q^-$. - Considering $y$'s, $B_y$ contsins at most $2((\frac{p_1+q_1}{2}-k)-(\frac{p_0+q_0}{2}+k)+1)=\Delta p+\Delta q-4k+2$, and similar for $B_x$. - Considering $y$'s, $C_y$ contsins at most $2(\frac{p_1+q_1-k}{2}-\frac{p_0+q_0+k}{2}+1)=\Delta p+\Delta q-2k+2$, and similar for $C_x$. Summing up, we get $$4n\leq 2k\cdot 4+ (\Delta p+\Delta q-4k+2)\cdot 2+(\Delta p+\Delta q-2k+2)\cdot 2=4(\Delta p+\Delta q)-4k+8$$Which implies $$n\leq \Delta p+\Delta q-k+2$$Also note that $n\leq 8k+2$, which means $\frac{n}{8}\leq k+\frac{1}{4}$. Summing up too, we get $$\frac{9}{8}n\leq \Delta P+\frac{9}{4}$$ Now calculate the perimeter: This is just some geometry. Note that 8 lines $y=y_0,y-x=q_0,x=x_1, x+y=p_1, y=y_1, y-x=q_1, x=x_0, x+y=p_0$ forms a convex octagon $Q=ABCDEFGH$ where $AB$ is $y=y_0$ and $BC$ is $y-x=q_0$, with lengths $$AB=2y_0-p_0-q_0, CD=p_1-q_0-2x_1, EF=p_1+q_1-2y_1, GH=2x_0+q_1-p_0$$And $$BC=(q_0+x_1-y_0)\sqrt{2}, DE=(x_1+y_1-q_1)\sqrt{2}, FG=(y_1-x_0-q_1)\sqrt{2}, HA=(p_0-x_0-y_0)\sqrt{2}$$Also, note that each side of the octagon has to contain at least 1 element of $S$, so $P\cap Q$ touches every side of $Q$: Say them $X_0,X_1,X_2,X_3,X_4,X_5,X_6,X_7$ with $X_0\in AB, X_1\in BC$. Then, since $P,Q$ and octagon $X=X_0X_1\cdots X_7$ are all convex, $$\ell(P)\geq \ell(P\cap Q)\geq \ell(X)$$Where $\ell(P)$ denotes perimeter of $P$. Now, use reflection to find minimum of $\ell(X)$. Reflect $Q$ in $BC$, and then reflect by $C^{(1)}D^{(1)}$, and then by $D^{(2)}E^{(2)}$, $\cdots$ and then by $A^{(7)}B^{(7)}$: Call this transformation $\psi$. Then using triangle inequality, we get $\ell(X)\geq X_0\psi(X_0)$. Also note that $\psi$ becomes just a translation: calculating the vector, it becomes $$(AB+CD+EF+GH)(1,0)+(BC+DE+FG+HA)(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})$$So, consider a triangle with 2 side lengths $a=AB+CD+EF+GH, b=BC+DE+FG+HA$ and the angle between them is $\frac{3}{4}\pi$. Then, by cosine law $$\ell(P)^2\geq (X_0\psi(X_0))^2=a^2+b^2+\sqrt{2}ab$$Substituting the lengths we get $a=2\Delta P-2\Delta X, b=(2\Delta X-\Delta P)\sqrt{2}$, and then it becomes $$a^2+b^2+\sqrt{2}ab=(2 \Delta P -2 \Delta X)^2 + 2(2 \Delta X-\Delta P)^2 + 2 (2 \Delta P - 2 \Delta X) (2 \Delta X - \Delta P)=2 \Delta P^2 - 4 \Delta P \Delta X + 4 \Delta X^2$$ Note that $\Delta P\geq \frac{9}{8}(n-2)$, and $\Delta X\geq (n-2)$. Therefore, $$\ell(P)\geq \sqrt{2 \Delta P^2 - 4 \Delta P \Delta X + 4 \Delta X^2}=\sqrt{\frac{2}{9}\Delta P^2+\frac{7}{4}\Delta X^2+\left(\frac{4}{3}\Delta P-\frac{3}{2}\Delta X\right)^{2}}\geq \sqrt{\frac{2}{9}\Delta P^{2}+\frac{7}{4}\Delta X^{2}}\geq\sqrt{\frac{65}{32}}(n-2)$$Since $\sqrt{\frac{65}{32}}>\sqrt{2}$, any positive real $\epsilon <\sqrt{\frac{65}{32}}-\sqrt{2}$ works. Hence the desired result.

IsoLyS wrote: First, I'll prove that $|S\cap A_p^+|+|S\cap A_p^-|+|S\cap A_q^+|+|S\cap A_q^-|+|S\cap B_y|+|S\cap B_x|+|S\cap C_y|+|S\cap C_x|\geq 4|S|$. It suffices to prove that these 8 region covers region $p_0\leq x+y\leq p_1$, $q_0\leq y-x\leq q_1$ at least four times. Very nice solution! I did not realize such a covering was possible. I used a somewhat different approach to give a bound on $\Delta p$ and $\Delta q$. Let $(x_1, y_1), \dots, (x_n, y_n)$ be the coordinates of the dots. Then each $x_i$, $y_i$, $x_i+y_i$, and $x_i-y_i$ can appear at most twice. We use the following identity. \[ \sum (x_i + y_i)^2 + \sum (x_i - y_i)^2 = 2 \sum x_i^2 + 2 \sum y_i^2 \]But because it becomes rather messy, I will carry out the computation using the variance. \[ \operatorname{Var}(x_i + y_i) + \operatorname{Var}(x_i - y_i) = 2 \operatorname{Var}(x_i) + 2 \operatorname{Var}(y_i) \]Since each value can be occupied by at most two $x_i$, and there are $n$ values, the variance $\operatorname{Var}(x_i)$ is minimized when all the $x_i$ are clustered. In this case, the variance is $n^2 / 48 + O(n)$, and it follows that \[ 2 \operatorname{Var}(x_i) + 2 \operatorname{Var}(y_i) \ge \frac{n^2}{12} + O(n). \]On the other hand, because $x_i + y_i$ are contained in the interval $[p_0, p_1]$ of size $\Delta p$, the variance $\operatorname{Var}(x_i + y_i)$ is maximized when they are divided into half and are clustered near the endpoints. (I'm handwaving, but the argument can be made rigorous.) The variance becomes $(\Delta p/2 - n/8)^2 + n^2/192 + O(n)$ in this case, and hence \[ \operatorname{Var}(x_i + y_i) + \operatorname{Var}(x_i - y_i) \le \Big( \frac{\Delta p}{2} - \frac{n}{8} \Big)^2 + \Big( \frac{\Delta q}{2} - \frac{n}{8} \Big)^2 + \frac{n^2}{96} + O(n). \]So it follows that \[ \Big( \Delta p - \frac{n}{4} \Big)^2 + \Big( \Delta q - \frac{n}{4} \Big)^2 \ge \frac{7n^2}{24} + O(n). \]