1. Найти точку с координатами, равными сред. арифм. координат данных точек (соответственно X и Y).
2. Вывести координаты точки (из числа введённых), самой ближайшей к полученной средней.
Координаты подаются на стандартный ввод, в массив их загонять нельзя — не пойдет по памяти. Количество точек задано.
P.S.: С первой частью программы все просто, а вот как оптимально сделать вторую, есть ли какие-нибудь идеи, кроме того, чтобы использовать файл? Иначе же никак? Ведь для нахождения ближайшей надо иметь доступ к координатам всех точек?
Здравствуйте, MitjaT, Вы писали:
MT>Даны до 500000 точек.
MT>1. Найти точку с координатами, равными сред. арифм. координат данных точек (соответственно X и Y).
MT>2. Вывести координаты точки (из числа введённых), самой ближайшей к полученной средней.
MT>Координаты подаются на стандартный ввод, в массив их загонять нельзя — не пойдет по памяти. Количество точек задано.
MT>P.S.: С первой частью программы все просто, а вот как оптимально сделать вторую, есть ли какие-нибудь идеи, кроме того, чтобы использовать файл? Иначе же никак? Ведь для нахождения ближайшей надо иметь доступ к координатам всех точек?
Элементарно. При вводе каждой новой точки корректируешь среднюю координату, соответственно запоминаешь ближайшую точку — ту которая была прежде или нововведенную
Здравствуйте, MitjaT, Вы писали:
MT>Даны до 500000 точек.
MT>1. Найти точку с координатами, равными сред. арифм. координат данных точек (соответственно X и Y).
MT>2. Вывести координаты точки (из числа введённых), самой ближайшей к полученной средней.
MT>Координаты подаются на стандартный ввод, в массив их загонять нельзя — не пойдет по памяти. Количество точек задано.
MT>P.S.: С первой частью программы все просто, а вот как оптимально сделать вторую, есть ли какие-нибудь идеи, кроме того, чтобы использовать файл? Иначе же никак? Ведь для нахождения ближайшей надо иметь доступ к координатам всех точек?
А есть какая-нибудь информация о распределении точек?
Или хотябы, в каких они пределах?
Здравствуйте, MitjaT, Вы писали:
MT>2. Вывести координаты точки (из числа введённых), самой ближайшей к полученной средней.
Чуется мне, что ты нас обманываешь. Т.е. чего-то недоговариваешь.
Найдем среднее арифметическое N-1 точки.
Утверждение: последней точкой мы можем сместить центр масс в любую точку плоскости (достаточно решить два линейных уравнения). Значит мы можем сместить его на место любой из N-1 ранее обсчитанных точек, т.е. эта ранее обсчитанная точка будет самой близкой (ближе некуда). А т.к. все N-1 точки запомнить нельзя, то задача неразрешима.
P.S. Внимательно еще раз прочти условие. Нет, не внимательно, а ОЧЕНЬ внимательно.
Здравствуйте, BlackHeretic, Вы писали:
BH>Элементарно. При вводе каждой новой точки корректируешь среднюю координату, соответственно запоминаешь ближайшую точку — ту которая была прежде или нововведенную
Здравствуйте, Tan4ik, Вы писали:
T>Здравствуйте, BlackHeretic, Вы писали:
BH>>Элементарно. При вводе каждой новой точки корректируешь среднюю координату, соответственно запоминаешь ближайшую точку — ту которая была прежде или нововведенную
T>(-1,0),(1,0),(3,0),(-7,0)
........
Нет, не обманываю, и даже не пытаюсь.
Я же писал:
"есть ли какие-нибудь идеи, кроме того, чтобы использовать файл?"
Т.е. нельзя записать в массив (из-за памяти), но можно в файл, но, конечно, не желательно, может быть критично по времени выполнения, но на крайний случай...
Здравствуйте, MitjaT, Вы писали:
MT>........ MT>Нет, не обманываю, и даже не пытаюсь. MT>Я же писал: MT>"есть ли какие-нибудь идеи, кроме того, чтобы использовать файл?" MT>Т.е. нельзя записать в массив (из-за памяти), но можно в файл, но, конечно, не желательно, может быть критично по времени выполнения, но на крайний случай...
Похоже без файла не обойтись
Обычно такие задачи дают на олимпиадах, где входные данные поступают из файла. И решаются они методом "N раз прочесть файл". В данном случае достаточно двух прочтений.
Здравствуйте, MitjaT, Вы писали:
MT>Даны до 500000 точек.
MT>1. Найти точку с координатами, равными сред. арифм. координат данных точек (соответственно X и Y).
MT>2. Вывести координаты точки (из числа введённых), самой ближайшей к полученной средней.
MT>Координаты подаются на стандартный ввод, в массив их загонять нельзя — не пойдет по памяти. Количество точек задано.
MT>P.S.: С первой частью программы все просто, а вот как оптимально сделать вторую, есть ли какие-нибудь идеи, кроме того, чтобы использовать файл? Иначе же никак? Ведь для нахождения ближайшей надо иметь доступ к координатам всех точек?
А можно вместо массива иметь ограниченный стека из наиболее подходящих точек, скажем размером в 10.
после заполнения стека наименее подходящая отбрасывается. В этом случае, если распределение точек не слишком отличается, то к концу прохода в стеке будет хранится искомое значение.
Естественно, чем стек больше тем меньше погрешность.
Можно решить задачу относительно параметра размера стека, определив его оптимальный размер, принимая условие, что в 99% в него должно попасть искомое значение.
Здравствуйте, tavr, Вы писали:
T>А можно вместо массива иметь ограниченный стека из наиболее подходящих точек, скажем размером в 10. T>после заполнения стека наименее подходящая отбрасывается.
Ну так Tan4ik ведь уже ж писал, что последняя точка может сместить центр масс в любую точку плоскости.
Здравствуйте, tavr, Вы писали:
T>В этом случае, если распределение точек не слишком отличается, то к концу прохода в стеке будет хранится искомое значение.
Вот и вот — если распределение точек не сильно отличается, а в условии про это ни слова. Т.е. по дефолту — ничем не ограничено
Здравствуйте, MitjaT, Вы писали:
MT>Даны до 500000 точек.
MT>1. Найти точку с координатами, равными сред. арифм. координат данных точек (соответственно X и Y).
MT>2. Вывести координаты точки (из числа введённых), самой ближайшей к полученной средней.
MT>Координаты подаются на стандартный ввод, в массив их загонять нельзя — не пойдет по памяти. Количество точек задано.
MT>P.S.: С первой частью программы все просто, а вот как оптимально сделать вторую, есть ли какие-нибудь идеи, кроме того, чтобы использовать файл? Иначе же никак? Ведь для нахождения ближайшей надо иметь доступ к координатам всех точек?
Используем среднее, полученное в первой задаче для решения второй.
ICQ [168117153]
