Задача на геометрию. Как быстро найти подходящую выборку элементов из матрицы?

Возьмем например второй пример
3 5
5 0
0 5
5 5
Оптимальный угол здесь будет примерно равен 45 градусам, при нем будет достигаться ответ 6.08761429

Нужно найти самую дальнюю дугу длиной R/N от всех жуков, а потом жука, который ближе всех к одному из краёв этой дуги.

Так как я угол перебираю с помощью бин.поиска, то по сути нам надо найти самую дальнюю точку от всех жуков. Самая дальняя точка - та точка, минимальное расстояние для которой будет как можно больше.
вот такая будет матрица расстояний. Число в i-ой строке, j-ом столбце - расстояние от i-ого жука, до j-ой точки

3.82683 3.82683 2.07107
6.08761 9.91445 10.505
9.91445 6.08761 10.505

Тут два кандидата на самую дальнюю точку - либо 0-ая, либо 1-ая. Но при этом так как ответ должен быть минимальным, то мы берем значение 3.82683, но это неправильно.

Задача на геометрию. Как быстро найти подходящую выборку элементов из матрицы?

Wataru , может быть попробовать использовать вместо алгоритма Куна алгоритм Диницы?

Задача на геометрию. Как быстро найти подходящую выборку элементов из матрицы?

Здравствуйте!
Спасибо, мне кажется это продвижение в правильную сторону
Единственное, тернарным поиском нельзя найти минимум, я построил график для второго примера,
тут показано как изменяется время добегания жука в зависимости от угла



На такой функции нельзя применить тернарный поиск, так как троичный поиск — метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.

А для бинарного поиска по производной не нужно искать производную, мы просто смотрим на значение функции f(x) в точке x и в точке f(x + eps). Если f(x) < f(x + eps), то сдвигаем r в точку x, (r = x) иначе сдвигаю l в точку x (l = x).



Реализовал, пока что ловлю TL3 (превышение по времени на 3-ем тесте), пока что думаю, как ускорять

Задача на геометрию. Как быстро найти подходящую выборку элементов из матрицы?

Здравствуйте!
Если взять такой пример 3 жука, 3 точки

1 2 3
4 5 6
7 8 9

То получится, что ближе всего к своей самой дальней точке прибежит 1-ый жук, за 3 единицы времени, но при этом остальные жуки добежать не усеют за 3 секунды даже до ближней точки

Python бот для Discord. Как реализовать?

Andrew, спасибо, что напомнили

Python бот для Discord. Как реализовать?

Решил часть проблемы, прилагаю код, для его работы скачайте ffmpeg.exe, этот код входит в канал и начинает играть музыку

import discord
from discord.ext import commands

TOKEN = 'ТОКЕН'

client = commands.Bot(command_prefix = '!')

@client.command()
async def startq(ctx):
    voicechannel = discord.utils.get(ctx.guild.channels, name='Название канала')
    vc = await voicechannel.connect()
    
    vc.play(discord.FFmpegPCMAudio(executable="путь к Ffmpeg.exe", source="путь к Test1.mp3"))

@client.event
async def on_ready():
    print('Logged in as')
    print(client.user.name)
    print(client.user.id)
    print('------')

client.run(TOKEN)

ABCPascal.Net. Олимпиадная задача, как ускорить код?

Антон Федорян, https://contest.yandex.ru/roi/contest/999/enter