|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
15.02.2016, 19:48 | #1 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Общая длина точек
Здравствуйте, нужна помощь.
Дано n точек, и их координаты. Нужно узнать общую длину между точками, учитывая, что некоторые точки могут лежать на одной прямой. То есть, если точки 2, 3, 4 лежат на одной прямой, то не нужно узнавать и добавлять расстояние между 2 и 3, 2 и 4, 3 и 4. Так то понятно, находит, подходит ли уравнение прямой, лежат ли точки на одной прямой, считаем и отнимаем. А вот что сделать, если на одной прямой более трех точек, ведь точек на одной прямой может быть хоть n. Помогите, пожалуйста, подскажите, может какой алгоритм не знаю. Вот код: Код:
|
15.02.2016, 20:08 | #2 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
И снова ссылку
|
15.02.2016, 20:30 | #3 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
и снова тот же, пятая.
http://olimpmoippo.pp.ua/ Последний раз редактировалось dimon_snake; 15.02.2016 в 21:47. |
16.02.2016, 01:00 | #4 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Код:
Ошибку пока не вижу Последний раз редактировалось Poma][a; 16.02.2016 в 01:06. |
16.02.2016, 01:15 | #5 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Можно, кстати, сделать что-то похожее на квадрат. Но это улучшит лишь время. А писанины больше. Да и лень мне..
|
16.02.2016, 19:08 | #6 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Спасибо. А можно подробнее о коде? Не особо знаю с++, переведу.
|
16.02.2016, 21:16 | #7 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Вот что хотелось бы узнать:
vector<point> v(n); - это создание массива v с элементами point, при это n элементов set<pair<point, point> > s; - это строку в паскале как можно представить, не пойму line l = line(v[i], v[j]); - вот эта не понятна, что за тип line if (s.find(make_pair(mi, ma)) == s.end()) - вот эта неясная s.insert(make_pair(mi, ma)); - и вот эта Все остальное вроде ясно |
16.02.2016, 22:42 | #8 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Пойми алгоритм и перепиши его как тебе захочется.
Set позволяет за логарифм вставлять и искать элемент Пара поинтов это все равно что структура с двумя полями first и second типа point |
17.02.2016, 18:17 | #9 |
Форумчанин
Регистрация: 05.11.2015
Сообщений: 167
|
Можете тогда просто объяснить алгоритм?
|
18.02.2016, 14:24 | #10 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Через каждые две точки проводишь прямую. Запоминаешь её. Ищешь на две самые удаленные точки - а затем плюсуешь расстояние между ними
И так делаешь для всех точек но важно проверить что прымую которую ты нашёл ты раньше не использовал Я делал это запоминая две точки. Можно это провернуть через общее уравнение прямой. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Даны координаты точек n на плоскости. Найти номера двух точек, расстояние между которыми наибольшее. | getredtm | Помощь студентам | 3 | 01.07.2013 01:47 |
Задаnm n точек. Найти m=3,4... точек и построить на них m-угольник: количество точек , лежащих внутри и вне его мин. различается | L.Rain | Помощь студентам | 0 | 11.12.2011 22:19 |
Даны координаты n точек на плоскости. Найти номера двух точек, расстояние между которыми наибольшее. | Viwwna | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 19.11.2011 06:33 |
дано два множества точек.Найти пересечение и разность этих множеств.Координаты точек X и Y вводить с клав | Degster | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 15.05.2011 18:32 |
определить радиус и центр окружности, на кот. лежит наиб.число точек заданного на плоскости мн-ва точек) | kcю | Помощь студентам | 0 | 17.11.2009 19:50 |