Let ~(x_0,y_0), \dots, (x_N,y_N)~ be the points where ~(x_0,y_0) = (0,0)~ is the starting point. We will compute ~A[i,j]~ and ~B[i,j]~ where ~A[i,j]~ is the cost to align with the ~i~ first points and end up at ~(x_i,y_j)~ and ~B[i,j]~ is the cost to align with the ~i~ first points and end up at ~(x_j,y_i)~. We have:

$$\displaystyle \begin{align*} A[i+1,j] &= \min\{A[i,j]+d[x_i,x_{i+1}], B[i,i+1]+d[y_i,y_j]\} \\ B[i+1,j] &= \min\{B[i,j]+d[y_i,y_{i+1}], A[i,i+1]+d[x_i,x_j]\} \end{align*}$$

The final answer is ~\min_j\{A[n,j], B[j,n]\}~.

Time complexity: ~\mathcal O(N^2)~