Для решения задачи необходимо считать входные данные и вывести выходные. Все. А теперь серьезно. Чтобы посчитать расстояние до точки можно воспользоваться формулой r*alpha, где r – радиус окружности, а alpha - угол в радианах, но и это здесь не требуется, так как в условии задачи явно указано, что расстояние можно определять углом. Вычислить расстояние между парами точек можно с помощью формулы min(|alpha1 - alpha2|, 360 - |alpha1 - alpha2|).*r Далее считается расстояние от i точки до всех остальных и суммируется. И так для каждой точки. Из всех сумм выбираются минимальные, и выводятся номера соответствующих точек в возрастающем порядке. Сложность такого алгоритма O(n2).
Примечание:
Многие участники попытались найти линейное или хотя бы логарифмическое решение, но из статистики видно, что оно совсем не тривиальное и у них не хватило техники на его реализацию. Некоторые участники некорректно обрабатывали случай, когда точка всего одна.
Заданы точки на окружности. Требуется выбрать две из них, чтобы сумма расстояний по окружности до всех остальных была минимальна.
На окружности расположено N точек. Их положение определяется углом φ между осью OX и радиусом, проведенным от центра окружности к этой точке. Угол задается в градусах. Никакие две точки на окружности не совпадают. Требуется среди данных точек найти такие, что сумма расстояний по окружности от каждой из этих точек до всех остальных была минимальна. Расстояние по окружности пропорционально минимальному углу, между радиусами, проведенными к этим точкам, поэтому сумму расстояний следует вычислять как сумму углов.
Формат входных данных
Первая строка файла содержит целое число N (1 ≤ N ≤ 360) - количество точек. Далее следует N строк: каждая строка содержит целое число φ (1 ≤ φ ≤ 360), определяющее положение точки на окружности.
Формат выходных данных
Первая строка файла содержит число K - количество точек, удовлетворяющих условию задачи. Далее следует K строк, содержащих номера этих точек в порядке считывания данных из файла. Номера точек требуется вывести в порядке возрастания номеров.
На окружности расположено N точек. Их положение определяется углом φ между осью OX и радиусом, проведенным от центра окружности к этой точке. Угол задается в градусах. Никакие две точки на окружности не совпадают. Требуется среди данных точек найти такие, что сумма расстояний по окружности от каждой из этих точек до всех остальных была минимальна. Расстояние по окружности пропорционально минимальному углу, между радиусами, проведенными к этим точкам, поэтому сумму расстояний следует вычислять как сумму углов.