Perl, 341 322 bytes

sub f{@g=map{sprintf"%03d",$_}0..$#_;$"=',';@l=grep{"@g"eq join$",sort/.../g}glob"{@g}"x(@i=@_);map{@c=/.../g;$s=0;$v=1;for$k(1..$#c){$s+=$D=d($k-1,$k);$_!=$k&&$_!=$k-1&&$D==d($_,$k)+d($_,$k-1)and$v=0 for 0..$#c}$m=$s if$m<$s&&$v}@l;$m}sub d{@a=@{$i[$c[$_[0]]]};@b=@{$i[$c[$_[1]]]};sqrt(($a[0]-$b[0])**2+($a[1]-$b[1])**2)} 

sub f { @g = map { sprintf"%03d",$_ } 0..$#_;  # generate fixed-width path indices $" = ','; # set $LIST_SEPARATOR to comma for glob @l = grep { # only iterate paths with unique points "@g" eq join $", sort /.../g # compare sorted indices with unique indices } glob "{@g}" x (@i=@_); # produce all permutations of path indices # and save @_ in @i for sub d map { @c = /.../g; # unpack the path indices $s=0; # total path length $v=1; # validity flag for $k (1..$#c) { # iterate path $s += # sum path length $D = d( $k-1, $k ); # line distance $_!=$k && $_!=$k-1 # except for the current line, && $D == d( $_, $k ) # if the point is on the line, + d( $_, $k-1 ) and $v = 0 # then reset it's validity for 0 .. $#c # iterate path again to check all points } $m=$s if $m<$s && $v # update maximum path length } @l; $m # return the max } sub d { @a = @{ $i[$c[$_[0]]] }; # resolve the index $_[0] to the first coord @b = @{ $i[$c[$_[1]]] }; # idem for $_[1] sqrt( ($a[0] - $b[0])**2 + ($a[1] - $b[1])**2 ) } 

• 322 bytes: save 19 by not resetting $", and some inlining

Perl, 341 322 318 bytes

sub f{@g=map{$_<10?"0$_":$_}0..$#_;$"=',';@l=grep{"@g"eq join$",sort/../g}glob"{@g}"x(@i=@_);map{@c=/../g;$s=0;$v=1;for$k(1..$#c){$s+=$D=d($k-1,$k);$_!=$k&&$_!=$k-1&&$D==d($_,$k)+d($_,$k-1)and$v=0 for 0..$#c}$m=$s if$m<$s&&$v}@l;$m}sub d{@a=@{$i[$c[$_[0]]]};@b=@{$i[$c[$_[1]]]};sqrt(($a[0]-$b[0])**2+($a[1]-$b[1])**2)} 

The code supports up to a 100 points. Since it produces all possible point permutations, 100 points would require at least 3.7×10¹³⁴ yottabytes of memory (12 points would use 1.8Gb).

sub f { @g = map { $_<10 ? "0$_" : $_ } 0..$#_; # generate fixed-width path indices $" = ','; # set $LIST_SEPARATOR to comma for glob @l = grep { # only iterate paths with unique points "@g" eq join $", sort /../g  # compare sorted indices with unique indices } glob "{@g}" x (@i=@_); # produce all permutations of path indices # and save @_ in @i for sub d map { @c = /../g;  # unpack the path indices $s=0; # total path length $v=1; # validity flag for $k (1..$#c) { # iterate path $s += # sum path length $D = d( $k-1, $k ); # line distance $_!=$k && $_!=$k-1 # except for the current line, && $D == d( $_, $k ) # if the point is on the line, + d( $_, $k-1 ) and $v = 0 # then reset it's validity for 0 .. $#c # iterate path again to check all points } $m=$s if $m<$s && $v # update maximum path length } @l; $m # return the max } sub d { @a = @{ $i[$c[$_[0]]] }; # resolve the index $_[0] to the first coord @b = @{ $i[$c[$_[1]]] }; # idem for $_[1] sqrt( ($a[0] - $b[0])**2 + ($a[1] - $b[1])**2 ) } 

• 322 bytes: save 19 by not resetting $", and some inlining
• 318 bytes: save 4 by reducing max nr of coords to 100.

Perl, 341 324 bytes

sub f{@g=map{sprintf"%03d",$_}0..$#_;$"=',';@l=grep{"@g"eq join$",sort/.../g}glob"{@g}"x(@i=@_);map{@c=/.../g;$s=0;$v=1;for$k(1..$#c){$s+=$D=d($k-1,$k);for(0..$#c){$v=0 if$_!=$k&&$_!=$k-1&&$D==d($_,$k)+d($_,$k-1)}}$m=$s if$m<$s&&$v}@l;$m}sub d{@a=@{$i[$c[$_[0]]]};@b=@{$i[$c[$_[1]]]};sqrt(($a[0]-$b[0])**2+($a[1]-$b[1])**2)} 

sub f { @g = map { sprintf"%03d",$_ } 0..$#_; # generate fixed-width path indices $" = ','; # set $LIST_SEPARATOR to comma for glob @l = grep { # only iterate paths with unique points "@g" eq join $", sort /.../g # compare sorted indices with unique indices } glob "{@g}" x (@i=@_); # produce all permutations of path indices # and save @_ in @i for sub d map { @c = /.../g; # unpack the path indices $s=0; # total path length $v=1; # validity flag for $k (1..$#c) { # iterate path $s += $D # sum path length = d( $k-1, $k );  # line distance   for ( 0..$#c ) { # iterate path again to check all points   $v=0  # reset validity, if $_!=$k && $_!=$k-1 # except for the current line ,  && $D == d( $_, $k ) # if the point is on the line  + d( $_, $k-1 )  } } $m=$s if $m<$s && $v # update maximum path length } @l; $m # return the max } sub d { @a = @{ $i[$c[$_[0]]] }; # resolve the index $_[0] to the first coord @b = @{ $i[$c[$_[1]]] }; # idem for $_[1] sqrt( ($a[0] - $b[0])**2 + ($a[1] - $b[1])**2 ) } 

• 324 bytes: save 17 by not resetting $", and some inlining

Perl, 341 322 bytes

sub f{@g=map{sprintf"%03d",$_}0..$#_;$"=',';@l=grep{"@g"eq join$",sort/.../g}glob"{@g}"x(@i=@_);map{@c=/.../g;$s=0;$v=1;for$k(1..$#c){$s+=$D=d($k-1,$k);$_!=$k&&$_!=$k-1&&$D==d($_,$k)+d($_,$k-1)and$v=0 for 0..$#c}$m=$s if$m<$s&&$v}@l;$m}sub d{@a=@{$i[$c[$_[0]]]};@b=@{$i[$c[$_[1]]]};sqrt(($a[0]-$b[0])**2+($a[1]-$b[1])**2)} 

sub f { @g = map { sprintf"%03d",$_ } 0..$#_; # generate fixed-width path indices $" = ','; # set $LIST_SEPARATOR to comma for glob @l = grep { # only iterate paths with unique points "@g" eq join $", sort /.../g # compare sorted indices with unique indices } glob "{@g}" x (@i=@_); # produce all permutations of path indices # and save @_ in @i for sub d map { @c = /.../g; # unpack the path indices $s=0; # total path length $v=1; # validity flag for $k (1..$#c) { # iterate path $s +=   # sum path length   $D = d( $k-1, $k ); # line distance    $_!=$k && $_!=$k-1 # except for the current line, && $D == d( $_, $k ) # if the point is on the line, + d( $_, $k-1 )  and $v = 0 # then reset it's validity  for 0 .. $#c # iterate path again to check all points } $m=$s if $m<$s && $v # update maximum path length } @l; $m # return the max } sub d { @a = @{ $i[$c[$_[0]]] }; # resolve the index $_[0] to the first coord @b = @{ $i[$c[$_[1]]] }; # idem for $_[1] sqrt( ($a[0] - $b[0])**2 + ($a[1] - $b[1])**2 ) } 

• 322 bytes: save 19 by not resetting $", and some inlining

Perl, 341 bytes

This is far from done, but it works. Supports up to 1000 coordinates, although the number of permutations probably pushes the limits (6 coordinates already takes a few seconds).

sub f{@i=@_;@g=map{sprintf"%03d",$_}0..$#_;$"=',';@l=glob"{@g}"x@_;$"=' ';map{@c=/.../g;$s=0;$v=1;for$k(1..$#c){$s+=$D=d($k-1,$k);for(0..$#c){if($_!=$k&&$_!=$k-1){$v=0 if$D==d($_,$k)+d($_,$k-1)}}}$m=$s if$m<$s&&$v}grep{"@g"eq join(' ',sort(/.../g))}@l;$m}sub d{@a=@{$i[$c[$_[0]]]};@b=@{$i[$c[$_[1]]]};sqrt(($a[0]-$b[0])**2+($a[1]-$b[1])**2)} 

sub f { @i = @_; @g = map { sprintf"%03d",$_ } 0..$#_;  # generate fixed-width path indices $"=',';@l=glob"{@g}"x@_;$"=' '; # produce all permutations of path indices  map {  @c = /.../g; # unpack the path indices $s=0; # total path length $v=1; # validity flag for $k (1..$#c) { # iterate path   $s += $D # sum path length = d( $k-1, $k ); # line distance    for (0..$#c) {  # iterate path again to check all points  if($_!=$k&&$_!=$k-1) { # except the current line    $v=0 # reset validity  if $D == # if the point is on the line  d( $_, $k )    +d( $_, $k-1 )  } }  }  $m=$s if $m<$s && $v # update maximum path length  }  grep{ "@g" eq join(' ',sort(/.../g) ) } # only iterate paths with unique points @l; $m  # return the max } sub d { #  @a=@{$i[$c[$_[0]]]};  # resolve the index $_[0] to the first coord   @b=@{$i[$c[$_[1]]]}; # idem for $_[1]   sqrt( ($a[0] - $b[0])**2 + ($a[1] - $b[1])**2 ) } 

print f( [0,1], [0,0], [1,0] ), $/; $m=0; print f( [0,0], [0,1], [1,0], [1,1] ), $/; $m=0; print f( [0,0], [0,1], [0,2] ), $/; $m=0; print f( [0,0], [0,1], [0,2], [1,0], [1,1], [1,2]),$/; $m=0; 

Perl, 341 324 bytes

sub f{@g=map{sprintf"%03d",$_}0..$#_;$"=',';@l=grep{"@g"eq join$",sort/.../g}glob"{@g}"x(@i=@_);map{@c=/.../g;$s=0;$v=1;for$k(1..$#c){$s+=$D=d($k-1,$k);for(0..$#c){$v=0 if$_!=$k&&$_!=$k-1&&$D==d($_,$k)+d($_,$k-1)}}$m=$s if$m<$s&&$v}@l;$m}sub d{@a=@{$i[$c[$_[0]]]};@b=@{$i[$c[$_[1]]]};sqrt(($a[0]-$b[0])**2+($a[1]-$b[1])**2)} 

sub f { @g = map { sprintf"%03d",$_ } 0..$#_; # generate fixed-width path indices $" = ',';  # set $LIST_SEPARATOR to comma for glob @l = grep {  # only iterate paths with unique points "@g" eq join $", sort /.../g # compare sorted indices with unique indices } glob "{@g}" x (@i=@_); # produce all permutations of path indices   # and save @_ in @i for sub d map {   @c = /.../g;   # unpack the path indices  $s=0; # total path length $v=1; # validity flag  for $k (1..$#c) { # iterate path   $s += $D # sum path length  = d( $k-1, $k ); # line distance    for ( 0..$#c ) { # iterate path again to check all points  $v=0 # reset validity,   if $_!=$k && $_!=$k-1 # except for the current line ,   && $D == d( $_, $k ) # if the point is on the line + d( $_, $k-1 )  }  }  $m=$s if $m<$s && $v # update maximum path length } @l; $m # return the max } sub d {    @a = @{ $i[$c[$_[0]]] }; # resolve the index $_[0] to the first coord @b = @{ $i[$c[$_[1]]] }; # idem for $_[1] sqrt( ($a[0] - $b[0])**2   + ($a[1] - $b[1])**2 )  } 

print f( [0,1], [0,0], [1,0] ), $/;  $m=0; # reset max for next call print f( [0,0], [0,1], [1,0], [1,1] ), $/; $m=0; print f( [0,0], [0,1], [0,2] ), $/;  $m=0; print f( [0,0], [0,1], [0,2], [1,0], [1,1], [1,2]),$/;  $m=0; 

• 324 bytes: save 17 by not resetting $", and some inlining