Beautiful problem Note that $f$ is a permutation. If there are no points $f$ with $f(X)=X$, then $f$ has an odd cycle $P_1\mapsto P_2\mapsto \cdots\mapsto P_{2k+1}\mapsto P_1$. Looking at the distances, we have $$P_1P_2\leqslant P_2P_3\leqslant\cdots P_{2k+1}P_1\leqslant P_1P_2$$hence all distances $d = P_iP_{i+1}$ are equal. Now only consider points $P_1,P_2,\ldots,P_{2k+1}$. We may WLOG assume that $d^2$ is not divisible by $4$ else we can just shrink the figure by half. For each $i$, let $P_i = (x_i,y_i)$. If $d^2$ is odd then $e_i = |x_i + y_i - x_{i+1} - y_{i+1}|$ is odd for all $i$. However, $e_1+e_2+\cdots+e_{2k+1}$ must be even, which is a contradiction. If $d^2 \equiv 2\pmod{4}$ then $|x_i-x_{i+1}|$ is always odd and we can use the same argument.

This is essentially the same as problem 28 on the shortlist of IMO 1990: https://artofproblemsolving.com/community/c3941_1990_imo_shortlist https://artofproblemsolving.com/community/c6h220964p1225290

But $n=3$ doesn't work. Imagine an equilateral triangle.

It is pretty well-known that there aren´t any equliateral triangles with integer coordinates

You're right , I forgot integer coordinates.

Lemma(Well known) :Let $q\in \mathbb Q$.Then $\cos q\pi\in \mathbb Q$ if and only if $\cos q\pi\in\{0,1,\pm\frac{1}{2},\pm1\}$ Proof. Let $z=\cos q\pi+i\sin q\pi$. Then $\frac{1}{2} (z+\frac{1}{z})=\cos q\pi$. Let $n$ be an integer such that,$qn\in\mathbb Z$.Then,It is easy to show that $z$ is aa root of $z^{2n}-1=0$.Hence ,$z$ is a algebric integer.Similarly one can show $z^{-1}$ is a algebric integer. So $z+\frac{1}{z}=2\cos q\pi$ is a algebric integer. Since ,$z+\frac{1}{z}=2\cos q\pi\in \mathbb Q$ so $z$ is a rational integer.so it must be in $\{0,\pm1,\pm2\}$. $\blacksquare$ Lemma: Let $n$ be an integer such that there exist a regular $n$-gon in the cartesian plane such that all of its vertices has integer lattices. Then $n=4$. Proof. Suppose FTSOC, there is an $n$ sided regular polygon with sidelength $a$ and $n\ne 4$ with all integger coordinate vertices. Let $A,B,C$ be three consecutive vertice of such polygon.It is clear that all of its external angle has measure $\alpha=\frac{2\pi}{n}$.Work on complex plane.WLOG,We may assumwe coordinate of A ,$A=0$.Let $BA$ makes angle $\theta$ with the positive direction of the $X$ axis. [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(12.cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -4., xmax = 8., ymin = -3., ymax = 6.; /* image dimensions */ pen qqwuqq = rgb(0.,0.39215686274509803,0.); draw(arc((0.,0.),0.4923747473276895,0.,39.98708810994527)--(0.,0.)--cycle, linewidth(2.) + qqwuqq); draw(arc((2.181745415893382,1.8298640878745016),0.4923747473276895,39.98708810994527,65.13445819700588)--(2.181745415893382,1.8298640878745016)--cycle, linewidth(2.) + red); /* draw figures */ draw((0.,5.)--(0.,-1.73671270506729), linewidth(1.2)); draw((-2.5,0.)--(7.46,0.), linewidth(1.2)); draw((0.,0.)--(2.181745415893382,1.8298640878745016), linewidth(0.4)); draw((3.3791031223704255,4.41341787338093)--(2.181745415893382,1.8298640878745016), linewidth(0.4)); draw((2.181745415893382,1.8298640878745016)--(5.0526279714356095,4.237718299746864), linewidth(0.4) + linetype("4 4")); draw((1.1973577064770438,2.583553785506428)--(0.,0.), linewidth(0.4)); /* dots and labels */ dot((0.,5.),linewidth(1.pt) + dotstyle); label("$Y$", (0.0703591271058203,5.02523382489966), NE * labelscalefactor); dot((0.,-1.73671270506729),linewidth(1.pt) + dotstyle); label("$Y'$", (0.0703591271058203,-1.7038877219121125), NE * labelscalefactor); dot((-2.5,0.),linewidth(1.pt) + dotstyle); label("$X'$", (-2.8018268989723687,-0.1118760388859126), NE * labelscalefactor); dot((7.46,0.),linewidth(1.pt) + dotstyle); label("$X$", (7.521630303331522,0.0358363853123946), NE * labelscalefactor); dot((0.,0.),linewidth(1.pt) + dotstyle); label("$A$", (-0.25789070444597273,-0.5221883283256549), NE * labelscalefactor); dot((2.181745415893382,1.8298640878745016),linewidth(1.pt) + dotstyle); label("$B$", (2.3024579816580126,1.1354733210109038), NE * labelscalefactor); label("$\theta$", (0.644796332321458,0.1835488095107018), NE * labelscalefactor,qqwuqq); dot((3.3791031223704255,4.41341787338093),linewidth(1.pt) + dotstyle); label("$C$", (3.4513323920892884,4.450796619684021), NE * labelscalefactor); label("$\alpha$", (2.515820372166678,2.3171727145973615), NE * labelscalefactor,red); dot((1.1973577064770438,2.583553785506428),linewidth(1.pt) + dotstyle); label("$C'$", (1.2684710122698648,2.612597562993976), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] Then $B$ has coordinate $a(\cos\theta+i\sin\theta)$.Next we will find the coordinate of $C$. Let $C'$ be the point through $A$ such that $AC'||BC$ and $AC'=a$.Then obviously $C'$ has coordinate $a(\cos(\theta+\alpha)+i\sin( \theta+\alpha))$. Then $C$ has coordinate $a(\cos(\theta+\alpha)+i\sin( \theta+\alpha))+a(\cos\theta+i\sin\theta)$. Putting $\alpha=\frac{2\pi}{n}$ We get $C$ has coordinate: $$(a(cos\frac{2\pi}{n}+1)\cos\theta-\sin\frac{2\pi}{n}\sin\theta+ia[(1+\cos\frac{2\pi}{n})sin\theta+\sin\frac{2\pi}{n}\cos\theta] $$ Since $A,B,C$ has integer coordinates so $$a(\cos\theta+i\sin\theta)\in\mathbb Z[i]$$$$a(cos\frac{2\pi}{n}+1)\cos\theta-\sin\frac{2\pi}{n}\sin\theta+ia[(1+\cos\frac{2\pi}{n})sin\theta+\sin\frac{2\pi}{n}\cos\theta]\in\mathbb Z[i]$$So $\cos\theta,\sin\theta$ are integers.Then $\tan\theta\in\mathbb Q$ Dividing real part ant imaginary part of the complex coordinate of $C$ by $\cos\theta$ we get : $$(cos\frac{2\pi}{n}+1)-\sin\frac{2\pi}{n}\tan\theta\in\mathbb Q$$$$(1+\cos\frac{2\pi}{n})\tan\theta+\sin\frac{2\pi}{n}\in\mathbb Q$$ But then,$\sin\frac{2\pi}{n}\in\mathbb Q $ and $\cos\frac{2\pi}{n}\in\mathbb Q$. So by the previous lemma,$$\cos\frac{2\pi}{n}\in\{0,\pm\frac{1}{2},\pm{1}\}$$Which in turn implies,$$\frac{2\pi}{n}\in\{\frac{2k+1}{2}\pi,(2k\pi\pm\frac{pi}{3},(2k\pi\pm\frac{2pi}{3},2k\pi,(2k+1)\pi\}\qquad\forall k\in \mathbb Z$$. From this one can easily verify that $n\{1,2,3.4,6\}$. $3,6$ can be eliminated,since for $n=6$ $\sin\frac{2\pi}{n}\in\mathbb R-\mathbb Q$. So $n=4$ is the only possible solution.Indeed,a square with vertices $(0,0),(0,1),(1,0),(0,0)$ is one example. $\blacksquare$ Coming back to the main problem,assume $f$ has no fixed point.Observe that $f$ is a bijection.Let $|AB|$ denote the length of $AB$. Now for all $A\in S$ there is a integer $m$ such that $f^m(A)=A$. But then,from the given condition: $$|Af(A)|\le |f(A)f^2(A)|\le\dots \le |f^{m-1}(A)A|\le |Af(A)|$$So indeed all the length are equal.Hence $S$ is union of some disjoint segments and regular polygons.As $|S|=\text{odd}$ so there is some regular polygon with odd number of sides and all vertices with integer coordinates.This contradicts the lemma.Hence $f$ has atleast one fixed point.$\blacksquare$

talkon wrote: Beautiful problem Note that $f$ is a permutation. If there are no points $f$ with $f(X)=X$, then $f$ has an odd cycle $P_1\mapsto P_2\mapsto \cdots\mapsto P_{2k+1}\mapsto P_1$. Looking at the distances, we have $$P_1P_2\leqslant P_2P_3\leqslant\cdots P_{2k+1}P_1\leqslant P_1P_2$$hence all distances $d = P_iP_{i+1}$ are equal. Now only consider points $P_1,P_2,\ldots,P_{2k+1}$. We may WLOG assume that $d^2$ is not divisible by $4$ else we can just shrink the figure by half. For each $i$, let $P_i = (x_i,y_i)$. If $d^2$ is odd then $e_i = |x_i + y_i - x_{i+1} - y_{i+1}|$ is odd for all $i$. However, $e_1+e_2+\cdots+e_{2k+1}$ must be even, which is a contradiction. If $d^2 \equiv 2\pmod{4}$ then $|x_i-x_{i+1}|$ is always odd and we can use the same argument. Does this even make sense? $d^2$ can't be $2 \pmod{4}$.

@above $d$ isn't necessarily an integer (although $d^2$ is).