Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Pascal/Delphi → Координати, визначення секторів
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
допоможіть з завданням:
маємо пари точок, які з'єднуються лініями. Потрібно знайти сектори які ними можна утворити, та зберегти у массив секторів, куди буди входити інформація про кожен з них, а саме координати вершин, якими він обмежовується
Я не зрозумів. Маємо пари точок - де на малюнку пари? Можна утворити - з трьох точок не на одній прямій можна утворити трикутник, але всі можливі трикутники будуть перетинатися. Ну і на малюнку ще деякі точки зі сторонами з'єднані - чи це точки на сторонах?
на малюнку ці пари вже з'єднані. Ось приклад вхідних данних:
(0;4) (3;4)
(3;4) (6;2)
(6;2) (6;0)
(8;1) (8;0) {не обовз'язково саме у такому вигляді}
з'єднувати можна тільки ті точки, які є введені. Тобто точку (3;4) можна з'єднати з (0;4) і (6;2).
Трикутник можна буде утворити, тільки якщо буде дано, що кожна з трьох точок буде з'єднуватись з двома іншими
fer123
А в чому проблема? Створіть двовимірний масив записів і вперед:
type
TPoint = record
Used: Boolean;
X, Y: Integer;
end;
TSector = array [1 .. n] of TPoint;
TMas = array [1 .. m] of TSector;
//...
Mas[i, j].Used := True;
ReadLn(Mas[i, j].X, Mas[i, j].Y);можна більш розгорнутий варіант з поясненнями?)
Навіть не знаю, що тут пояснювати. Просто складаєте різні типи одне в одне, поки не вийде зручна для роботи структура. Трохи докладніше отут: http://pascal.org.ua/structure-types#array
Ну а далі уже придумуєте до неї алгоритм.
Тобто лінії між точками задано вхідними даними, і свої добудовувати не можна?
1. Ви, як я розумію, некоректно використовуєте слово "можна". У вас є точки, з'єднані відрізками, а ви кажете - "можна з'єднати". "Можна" означає, що можна і не з'єднувати.
2. Чи можуть відрізки перетинатися не в перелічених точках? З умови незрозуміло.
3. Не до кінця зрозуміло, що вважається "сектором". Сектор може не торкатися боку аркуша?
Якщо відповіді на 2 і 3 - "ні", то задача зводиться до пошуку мінімальних циклів. Десь так:
- перетворюємо масив точок на граф (матриця інцидентності чи ще якось, за бажання, аби лиш був нормальний пошук сусідніх вершин), додаємо ребра на краях аркуша.
- по одній обираємо ребра на краях, шукаємо перебором мінімальний цикл із цим ребром, запам'ятовуємо цикл і викидаємо ребро з графу.
- цикли і будуть секторами.
Тобто лінії між точками задано вхідними даними, і свої добудовувати не можна?
так.
1. "Можна" означає, що можна і не з'єднувати.
обов'язково з'єднувати
2. Чи можуть відрізки перетинатися не в перелічених точках?
ні
3. Сектор може не торкатися боку аркуша?
може
Тоді найлегше, мабуть, реально визначати області.
1. Додаємо відрізки на краях аркуша, можливо, з кутами, для форми.
2. Беремо відрізок, прив'язуємо до нього області inner=1 ("внутрішня") і new=2 ("нова"). Беремо одну його вершину і ідемо з неї за годинниковою стрілкою (сортуємо всі відрізки, що виходять з точки, беремо найближчий проти г.с., якщо відрізків більше 2, прив'язуємо до нього сектори inner і new:=new+1, якщо менше, inner і new, якщо вже є прив'язані сектори - то або все гаразд, або асоціюємо прив'язаний сектор із якимось inner і замінюємо більший з них на менший у всіх відрізків). Беремо наступну точку і т.д.
Це в загальних рисах, ніби має працювати. Що незрозуміло - уточнюйте.
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися