-- Doesnt work properly from tests

-- Calculates optimal x,y,z coordinates for a diameter to hold most players
-- returns nothing if no coords or random pic is as good

local function distsort(a, b)
    return a[2] < b[2]
end

local function GetPosition(players, diameter)
    if #players <= 1 then
        return
    end

    -- Save everyone's distance to everyone to distances (its a 2d matrix)
    -- Save the sum distance to everyone and the index to maxdists
    local distances = {}
    local maxdists = {}
    for k1,v1 in ipairs(players) do
        distances[k1] = {}
        local distsum = 0

        for k2,v2 in ipairs(players) do
            local curdist = v1:GetExactDistance2d(v2)
            distances[k1][k2] = curdist
            distsum = distsum + curdist
        end

        maxdists[#maxdists+1] = {k1, distsum/2} -- divide by 2 since
    end

    -- Need to throw away one by one until one remains so max count-1 times
    for i = 1, #maxdists-1 do
        -- Always sort first so maximum distance element is at top
        table.sort(maxdists, distsort)

        -- if maximum distance is within the diameter allowed then stop
        if maxdists[#maxdists][2] <= diameter then
            break
        end

        local maxelem = maxdists[#maxdists]
        local elemdists = distances[maxelem[1]]
        maxdists[#maxdists] = nil-- throw max element away

        -- decrease everyone's max distance by their distance from the element thrown away
        for k,v in ipairs(maxdists) do
            v[2] = v[2] - elemdists[v[1]]
        end
    end

    if #maxdists <= 1 then
        return
    end

    -- calculate average 2d coords
    local x,y,z = 0,0,0
    for k,v in ipairs(maxdists) do
        local ox, oy, oz = players[v[1]]:GetLocation()
        x = x+ox
        y = y+oy
        z = z+oz
        print(v[1])
    end
    return x/#maxdists, y/#maxdists, z/#maxdists
end

local Player = {}
Player.__index = Player

function Player:GetLocation()
    return self.x, self.y, self.z
end

function Player:GetExactDistance2d(player)
    local x = self.x - player.x
    local y = self.y - player.y
    return math.sqrt(x*x + y*y)
end

function Player:new(x, y, z)
    return setmetatable({x=x, y=y, z=z}, Player)
end

local players = {
    Player:new(6.4, 8, 6),
    Player:new(4, 2, 7),
    Player:new(3, 2, 3),
    Player:new(18, 86, 100),
}

local x,y,z = GetPosition(players, 1)
print(x,y,z)

for k,v in ipairs(players) do
    print(k, v:GetExactDistance2d({x=x, y=y, z=z}))
end