convex3.go

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

type Point struct {
	x float64
	y float64
}

func Dist(a, b Point) float64 {
	return math.Sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y))
}

func makeSplitTable(n int) [][]float64 {
	s := make([][]float64, n)
	for i := 0; i < n; i++ {
		s[i] = make([]float64, n)
		for j := 0; j < n; j++ {
			s[i][j] = math.MaxFloat64
		}
	}
	return s
}

func Triangulate(p []Point) float64 {
	s := makeSplitTable(len(p))

	//Give existing edges length 0
	for v1 := 0; v1 < len(p); v1++ {
		v2 := (v1 + 1) % len(p)
		s[v1][v2] = 0.0
	}

	for stride := 2; stride <= len(p)-2; stride++ {
		for v1 := 0; v1 < len(p); v1++ {
			v2 := (v1 + stride) % len(p)
			for v3_ := 0; v3_ < stride-1; v3_++ {
				v3 := (v1 + 1 + v3_) % len(p)
				length := Dist(p[v1], p[v2]) + s[v1][v3] + s[v3][v2]
				if length < s[v1][v2] {
					s[v1][v2] = length
				}
			}
		}
	}

	best_length := math.MaxFloat64
	for v1 := 0; v1 < len(p); v1++ {
		//2-behind, containing all rest of poly
		v2 := (v1 + len(p) - 2) % len(p)
		if s[v1][v2] < best_length {
			best_length = s[v1][v2]
		}
	}

	return best_length
}

func main() {
	//Because apparently Scanf skips characters on the stdin without wrapping it
	stdin := bufio.NewReader(os.Stdin)

	n := -1
	_, err := fmt.Fscanf(stdin, "%d\n", &n)
	if err != nil {
		fmt.Printf("Scanning error: %s\n", err.Error())
		return
	}

	points := make([]Point, n)
	for i := 0; i < n; i++ {
		_, err = fmt.Fscanf(stdin, "%f%f", &(points[i].x), &(points[i].y))
		if err != nil {
			fmt.Printf("Scanning error: %s\n", err.Error())
			return
		}
	}
	best := Triangulate(points)
	fmt.Printf("%.4f\n", best)
}