Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
0 / 0 / 0
Регистрация: 16.07.2013
Сообщений: 20
1

Найти выпуклую оболочку множества

17.07.2013, 20:15. Показов 1581. Ответов 1
Метки нет (Все метки)

Задано множество N точек. Ai=1..N.Найти выпуклую оболочку этого множества,т.е. те точки,которые являются крайними.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.07.2013, 20:15
Ответы с готовыми решениями:

Задано множество точек в трехмерном пространстве, найти выпуклую оболочку наименьшего объема
Задано множество точек в трехмерном пространстве. Найти его выпуклую оболочку, то есть множество...

Ввести три множества через один файл и найти множества их объединения и пересечения
Нужно ввести три множества через один файл и найти множества их объединения и...

Найти выпуклую оболочку множества
Всем привет. Задача - найти выпуклую оболочку множества (крайние точки множества, образующие...

Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества
Заданное множество точек на плоскости. Найти выпуклую оболочку этого множества, то есть выпуклый...

1
Модератор
64059 / 47474 / 32728
Регистрация: 18.05.2008
Сообщений: 115,185
17.07.2013, 20:37 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Вот программа с графикой, сам переделаешь.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
{ Построение выпуклой оболочки множества }
uses crt,graph;
type TPoint=record
            x,y: real;
            end;
     Tvyp=record
          x,y:real;
          k:integer;{номер точки}
          end;
 
const maxn=100;
 
{находится ли точка левее луча}
function IsLeft(p,p1,p2:TPoint):boolean;
begin
IsLeft:=(p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x)>0;
end;
 
var n,m,i,t1,t,newt:integer;
    x0,y0:integer;
    ms:real;
    s:string;
    p:array [1..maxn] of TPoint; {Точки множества}
    p1:array [1..maxn] of TVyp; {Точки выпуклой оболочки}
    used:array [1..maxn] of boolean;{Принадлежит-не принадлежит оболочке}
begin
clrscr;
randomize;
write('Количество точек n=');
readln(n);
writeln('Множество точек:');
for i:=1 to n do
 begin
  p[i].x:=-10+20*random;
  p[i].y:=-10+20*random;
  write('P[',i:2,'](',p[i].x:5:2,';',p[i].y:5:2,')  ');
  if i mod 4=0 then writeln;
 end;
t1:=1;{первая точка}
for i:=1 to n do
 begin
  if (p[i].y<p[t1].y) then t1:=i else
  if (p[i].y=p[t1].y) and (p[i].x<p[t1].x) then t1:=i;
 end;
FillChar(used,SizeOf(used),false);
writeln;
writeln;
writeln('Выпуклая оболочка идет через вершины: ');
t:=t1;
m:=0;
repeat
m:=m+1;
p1[m].x:=p[t].x;p1[m].y:=p[t].y;p1[m].k:=t;
used[t]:=true;
newt:=0;
{ Поиск следующей вершины }
for i:=1 to n do
if i<>t then
if (newt=0) or (IsLeft(p[t], p[i], p[newt]))then newt:=i;
t:=newt;
until t=t1;
for i:=1 to m do
write('P[',p1[i].k:2,'](',p1[i].x:5:2,';',p1[i].y:5:2,')  ');
if i mod 4=0 then writeln;
m:=m+1;
p1[m].x:=p1[1].x;p1[m].y:=p1[1].y;{замкнем оболочку}
writeln;
writeln;
write('Нажмите Enter для проверки результата графически');
readln;
initgraph(x0,y0,'');
x0:=getmaxX div 2;
y0:=getmaxY div 2;
ms:=(y0-10)/10;
line(x0-y0+10,y0,x0+y0-10,y0);
outtextXY(x0+y0,y0-15,'X');
line(x0,10,x0,getmaxY-10);
outtextXY(x0+5,10,'Y');
outtextXY(x0+5,y0+15,'0');
for i:=1 to 10 do
 begin
  line(x0-3,y0-round(i*ms),x0+3,y0-round(i*ms));{засечки на оси У}
  line(x0-3,y0+round(i*ms),x0+3,y0+round(i*ms));
  line(x0+round(i*ms),y0-3,x0+round(i*ms),Y0+3); {засечки на оси Х}
  line(x0-round(i*ms),y0-3,x0-round(i*ms),Y0+3);
  str(i,s);
  {подпись оси У}
  outtextXY(x0-35,y0-round(i*ms),s);{соответственно засечкам}
  outtextXY(x0-35,y0+round(i*ms),'-'+s);
  {подпись оси Х}
  outtextXY(x0+round(i*ms),y0+10,s);
  outtextXY(x0-round(i*ms),y0+10,'-'+s);
 end;
setcolor(14);
moveto(x0+round(p1[1].x*ms),y0-round(p1[1].y*ms));
for i:=1 to m do
lineto(x0+round(p1[i].x*ms),y0-round(p1[i].y*ms));
setcolor(12);
for i:=1 to n do
 begin
  circle(x0+round(p[i].x*ms),y0-round(p[i].y*ms),1);
  str(i,s);
  outtextXY(x0+round(p[i].x*ms)+5,y0-round(p[i].y*ms),s);
 end;
readln
end.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.07.2013, 20:37

Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую
Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их...

Построить выпуклую замкнутую оболочку
Построить выпуклую замкнутую оболочку y=1-x^(4/5)

пжста найдите ошибку в задаче на выпуклую оболочку
Здравствуйте,уже 2 дня не могу найти ошибку в коде,валится на 5 тесте. Задача: Даны точки(их...

Найти линейную оболочку векторов
Найти линейную оболочку векторов - элементов векторного пространства (2,2) - матриц: A=...

Найти проекцию вектора на линейную оболочку
дан вектор x = (14,16,2,5) . Нужно найти проекцию вектора x на L = (a,b) где a = (7,3,1,2) b =...

помогите найти подходящую оболочку под C++
Привет всем ! Проконсультируйте пожалуйста меня по поводу оболочек под C++ Дело в том, что я...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.