1 Востаннє редагувалося fer123 (19.01.2014 15:27:55)

Тема: Координати, визначення секторів

допоможіть з завданням:
маємо пари точок, які з'єднуються лініями. Потрібно знайти сектори які ними можна утворити, та зберегти у массив секторів, куди буди входити інформація про кожен з них, а саме координати вершин, якими він обмежовується
http://s3.hostingkartinok.com/uploads/thumbs/2014/01/82e40ebd55f6502d40bb890ae3c9b4a8.png

Post's attachments

tabl1.jpg 42.76 kb, 87 downloads since 2014-01-17 

2

Re: Координати, визначення секторів

Я не зрозумів. Маємо пари точок - де на малюнку пари? Можна утворити - з трьох точок не на одній прямій можна утворити трикутник, але всі можливі трикутники будуть перетинатися. Ну і на малюнку ще деякі точки зі сторонами з'єднані - чи це точки на сторонах?

3

Re: Координати, визначення секторів

на малюнку ці пари вже з'єднані. Ось приклад вхідних данних:
(0;4) (3;4)
(3;4) (6;2)
(6;2) (6;0)
(8;1) (8;0)  {не обовз'язково саме у такому вигляді}

з'єднувати можна тільки ті точки, які є введені. Тобто точку (3;4) можна з'єднати з (0;4) і (6;2).
Трикутник можна буде утворити, тільки якщо буде дано, що кожна з трьох точок буде з'єднуватись з двома іншими

4

Re: Координати, визначення секторів

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);
Подякували: fer1231

5

Re: Координати, визначення секторів

можна більш розгорнутий варіант з поясненнями?)

6 Востаннє редагувалося Torbins (18.01.2014 19:05:35)

Re: Координати, визначення секторів

Навіть не знаю, що тут пояснювати. Просто складаєте різні типи одне в одне, поки не вийде зручна для роботи структура. Трохи докладніше отут: http://pascal.org.ua/structure-types#array
Ну а далі уже придумуєте до неї алгоритм.

7

Re: Координати, визначення секторів

ну мене більше цікавить сам алгоритм

8

Re: Координати, визначення секторів

Тобто лінії між точками задано вхідними даними, і свої добудовувати не можна?

9

Re: Координати, визначення секторів

1. Ви, як я розумію, некоректно використовуєте слово "можна". У вас є точки, з'єднані відрізками, а ви кажете - "можна з'єднати". "Можна" означає, що можна і не з'єднувати.
2. Чи можуть відрізки перетинатися не в перелічених точках? З умови незрозуміло.
3. Не до кінця зрозуміло, що вважається "сектором". Сектор може не торкатися боку аркуша?
Якщо відповіді на 2 і 3 - "ні", то задача зводиться до пошуку мінімальних циклів. Десь так:
- перетворюємо масив точок на граф (матриця інцидентності чи ще якось, за бажання, аби лиш був нормальний пошук сусідніх вершин), додаємо ребра на краях аркуша.
- по одній обираємо ребра на краях, шукаємо перебором мінімальний цикл із цим ребром, запам'ятовуємо цикл і викидаємо ребро з графу.
- цикли і будуть секторами.

10

Re: Координати, визначення секторів

Torbins написав:

Тобто лінії між точками задано вхідними даними, і свої добудовувати не можна?

так.

11

Re: Координати, визначення секторів

koala написав:

1.  "Можна" означає, що можна і не з'єднувати.

обов'язково з'єднувати

2. Чи можуть відрізки перетинатися не в перелічених точках?

ні

3.  Сектор може не торкатися боку аркуша?

може

12

Re: Координати, визначення секторів

Тоді найлегше, мабуть, реально визначати області.
1. Додаємо відрізки на краях аркуша, можливо, з кутами, для форми.
2. Беремо відрізок, прив'язуємо до нього області inner=1 ("внутрішня") і new=2 ("нова"). Беремо одну його вершину і ідемо з неї за годинниковою стрілкою (сортуємо всі відрізки, що виходять з точки, беремо найближчий проти г.с., якщо відрізків більше 2, прив'язуємо до нього сектори inner і new:=new+1, якщо менше, inner і new, якщо вже є прив'язані сектори - то або все гаразд, або асоціюємо прив'язаний сектор із якимось inner і замінюємо більший з них на менший у всіх відрізків). Беремо наступну точку і т.д.
Це в загальних рисах, ніби має працювати. Що незрозуміло - уточнюйте.