Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 26.01.2014, 13:43   #1
Dragon65
Пользователь
 
Регистрация: 26.01.2014
Сообщений: 18
По умолчанию Задача на Паскаль: по заданному множеству N точек построить N-угольник

Имеется робот,который,глядя на множество точек, легко определяет их координаты в координатном множестве, необходимо составить программу,которая учит робота соединять точки так, чтобы получился ЛЮБОЙ N-угольник,без самопересечний и "усов".
На вход программе подается число N(от 3 до 1000000) всех точек.
И координаты в N строчках всех точек x и y (от -1000 до 1000)

Вывести последовательность номеров точек в котором нужно их соединять чтобы получить N-угольник. Если решений несколько, то вывести любое.Гарантируется, что все точки различны и ни какие 3 не лежат на 1 прямой.

Пример:
Input
7(кол-во точек)
2 3 (x_y первой точки)
3 2
5 1
5 3
6 2
4 2
4 3
Output
3 5 4 7 6 1 2
На мой взгляд это сложная задача, можете подсказать как решать и её вообще можно решить на языке Pascal?
Я думал создать цикл,в котором анализируется принадлежность каждой точки только к вершинам двух прямых,но учитывая количество точек это как то неразумно вроде... -или без этого анализа не обойтись?
Сколько точек, столько и сторон многоугольнике,думаю в конце можно поставить условие чтобы сторон было столько же сколько точек (N)
Dragon65 вне форума Ответить с цитированием
Старый 26.01.2014, 13:47   #2
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Дайте ссыль на задачу..

Я бы расчитывал по формуле угол и ходил по нему..
Poma][a вне форума Ответить с цитированием
Старый 26.01.2014, 14:27   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Можно таким путем - добавить еще одну точку не совпадающую с заданными и лежащую внутри выпуклой оболочки, охватывающей все точки. Впрочем последнее и не важно. Отсортировать по углам и расстояниям от этой точки до всех остальных и соединить отрезками по результатам сортировки
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 26.01.2014, 14:33   #4
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Кстати, если строить правильные N-угольники? На окружности рисовать окружности радиусом 2PiR/N.. Сначала из произвольной точки, далее из точки пересечения этой окружности с большой..
Poma][a вне форума Ответить с цитированием
Старый 26.01.2014, 14:37   #5
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Правильные слабо будет построить по произвольным точкам. Или о чем-то другом речь идет?
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 26.01.2014, 14:38   #6
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Правильные слабо будет построить по произвольным точкам. Или о чем-то другом речь идет?
Ну да.. кто-то надеясь на телепатор не стал читать условие.. Простите..
Poma][a вне форума Ответить с цитированием
Старый 26.01.2014, 15:24   #7
Dragon65
Пользователь
 
Регистрация: 26.01.2014
Сообщений: 18
По умолчанию

Добавить точку внутри выпуклой оболочки, это интересно, но как узнаем что эта точка именно внутри оболочки? допустим если точек максимум,10^6(миллион), нужно всё равно чтобы N-угольник получился.
Если выбирать эту точку со случайными координатами наверно должно быть условие, когда эта точка лежит не внутри оболочки, а произойдет самопересечение,это можно как-то учесть?

Может быть очень много случаев расположений N-угольника,т.к. сказано что он любой, и в некоторых случаев, соединяя заданные точки с внутренней Вашей точкой, произойдет пересечение с самой фигурой,это влияет на что-нибудь?
Dragon65 вне форума Ответить с цитированием
Старый 26.01.2014, 15:32   #8
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Про выпуклую оболочку я загнул, можно в любом месте. Главное, что бы не совпадала с точкой из множества. Про сортированные углы - на бумаге из этой точки провелись бы лучи во все остальные точки. На некоторых из них возможно попадут точки. И начиная с конечной точки любого луча по часовой стрелке соединяем отрезком с самой ближней к нашей лишней точке точку на соседнем луче и т.д. Хоть триллионы точек. Самопересечений не предвидится
Цитата:
соединяя заданные точки с внутренней Вашей точкой
Эта левая точка вообще-то ни с чем и не будет соединяться в конечном счете, а нужна только для алгоритма
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 26.01.2014 в 15:35.
Аватар вне форума Ответить с цитированием
Старый 26.01.2014, 16:16   #9
Dragon65
Пользователь
 
Регистрация: 26.01.2014
Сообщений: 18
Радость

действительно,т.е. из 1 любой точки, не совпадающей с точкой множества выходит бесконечное множество различных лучей,на некоторые точно попадут всё наши точки и их нужно просто соединять.
Но этих лучей будет много,в случае большого числа точек(N)-это каждый луч придется задавать и смотреть углы между выходящими из "пробной" точки? -Соединять придется те точки, у которых между лучами наименьший угол-скалярное произведение?

"пробную" точку мы задаем сами далее в цикле от 1 до N нужно будет брать модули двух лучей и разность координат x и y точек, cos(a)=(ab)/(|a||b|)-для первых 2 точек,не факт ,что ещё их придется соединять,далее определяем косинус м/у первой и 3-ей точкой, м/у 1 и 4-ой,м/у 1 и 5-ой и т.д. до N и при этом сравниваем их.

Но чтобы программа в цикле for i:=1 to N do...
под 1 понимала координаты первой точки допустим, нужен массив?
Вывести придется N цифр в правильном порядке, если N очень большое, то N переменных завести не получится,как тут быть?

Последний раз редактировалось Dragon65; 26.01.2014 в 17:04.
Dragon65 вне форума Ответить с цитированием
Старый 26.01.2014, 18:17   #10
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 19,042
По умолчанию

Цитата:
из 1 любой точки, не совпадающей с точкой множества выходит бесконечное множество различных лучей
Бесконечное и не нужно, а нужны именно конкретные лучи. Да, и немного подумал, все таки произвольная точка не прокатит, ибо будет проблема соединения начала и конца. Но и выпуклая оболочка не нужна. А нужна точка, координаты которой попадают в MinMax предложенного множества точек
Цитата:
чтобы программа в цикле
В одном цикле рассчитываем углы. Дальше примитивная сортировка и в цикле выдача номеров точек. Ну и точку придумать с проверкой на не совпадения с предложенными, тоже цикл и возможно вложенный в другой
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию

Последний раз редактировалось Аватар; 26.01.2014 в 18:22.
Аватар вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Delphi. На плоскости заданы n точек своими координатами.Построить квадрат Allexey Помощь студентам 4 18.06.2013 13:46
Задаnm n точек. Найти m=3,4... точек и построить на них m-угольник: количество точек , лежащих внутри и вне его мин. различается L.Rain Помощь студентам 0 11.12.2011 22:19
задача по множеству Марийка92 Помощь студентам 0 20.04.2011 11:07
Построить на экране множество точек Lange Помощь студентам 0 05.10.2010 22:09
(С++)построить окружность, проходящую через k>=3 точек каждого из двух множеств... Suitable Помощь студентам 1 18.01.2009 23:19