We can use a similar argument as in the proof of rearrangement inequality. Letting $f(x,y)=\sqrt{x^2+Cxy+y^2}$, it suffices to show the case $n=2$, which corresponds to a single transposition in the general case. Al we have to show that if $a<b$ and $c<d$, then $$\sqrt{a^2+Cac+c^2}+\sqrt{b^2+Cbd+d^2}<\sqrt{a^2+Cad+d^2}+\sqrt{b^2+Cbc+c^2}$$Since $C\in(-2,2)$ we can write it as $C=-2\cos\theta$ for some $\theta\in(0,\pi)$. Therefore we can interpret $f(x,y)$ as the distance $XY$ of the points $X$ and $Y$ on two halflines with an angle $\theta$ between them, with the same origin $O$, so that $OX=x$ and $OY=y$. So if $O,A,B$ are on the half line $Or$ in this order and $O,C,D$ in this order on the half line $Os$, it suffices to show $AC+BD<AD+BC$. To do this simply pick $X=AD\cap BC$, and by triangle inequality we have the strict inequality $$AC+BD<AX+CX+BX+DX=AD+BC$$as wanted.