Развяжите задание

[Ivanna]

1. Из Одесского порта в город Тернополь на фабрику мебели "Новая" необходимо перевезти N разных грузов (0<n<=50). Грузоподъемность автомобиля, которой будет осуществляться перевозка k тон(0<k<=50). Ва6нтажі пронумерованы и информация о весе каждого из грузов хранится в массиве М[N]. Определить, сколько рейсов необходимо сделать автомобилю при условии, что грузы неразделимы. (Допускают что вес отдельно взятого груза не превышает К тон.)
Можно рассмотреть частичный случай когда грузы перевозятся только в порядке их нумерации
2. Задана точка с координатами (x, y) и треугольник с координатами вершин(x1, y1) (x2, y2) (x3, y3). Определить, лежит ли точка внутри или снаружи треугольника

[alex_8]

Решение второй задачи

A(x1;y1) B(x2;y2) C(x3;y3) D(x,y)
1) Находишь площадь треугольника ABC
S = |x1(y2-y3)+x2(y3-y1)+x3(y1-y2)|/2
2) Находишь площадь ABD
S = |x1(y2-y)+x2(y-y1)+x(y1-y2)|/2
3) Находишь площадь BCD
S = |x (y2-y3)+x2(y3-y)+x3(y-y2)|/2
4) Находишь площадь CAD
S = |x1(y-y3)+x(y3-y1)+x3(y1-y)|/2
Складываешь ABD+BCD+CAD
делаешь проверку если ABD+BCD+CAD=ABC
тогда точка лежит внутри если нет тогда снаружи.

[Ivanna]

Сообщение от alex_8

Решение второй задачи

A(x1;y1) B(x2;y2) C(x3;y3) D(x,y)
1) Находишь площадь треугольника ABC
S = |x1(y2-y3)+x2(y3-y1)+x3(y1-y2)|/2
2) Находишь площадь ABD
S = |x1(y2-y)+x2(y-y1)+x(y1-y2)|/2
3) Находишь площадь BCD
S = |x (y2-y3)+x2(y3-y)+x3(y-y2)|/2
4) Находишь площадь CAD
S = |x1(y-y3)+x(y3-y1)+x3(y1-y)|/2
Складываешь ABD+BCD+CAD
делаешь проверку если ABD+BCD+CAD=ABC
тогда точка лежит внутри если нет тогда снаружи.

А как ето все написать в паскале?

[ROMA2PVT]

{Задана точка с координатами (x, y) и треугольник с координатами
вершин(x1, y1) (x2, y2) (x3, y3).
Определить, лежит ли точка внутри или снаружи треугольника.}
Uses
  CRT;
var
  x,y,x1,x2,x3,y1,y2,y3:real;
  s,s1,s2,s3:real;
Begin
Clrscr;
write('Введите A: ');
readln(x1);
readln(y1);
write('Введите B: ');
readln(x2);
readln(y2);
write('Введите С: ');
readln(x3);
readln(y3);
write('Введите координаты точки: ');
readln(x);
readln(y);
If (x1=x2) and (x3=x1) or (y1=y2) and (y2=y3) then
write('Неверные координаты!')
else
begin
s:=1/2*abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));
s1:=1/2*abs((x2-x1)*(y-y1)-(x-x1)*(y2-y1));
s2:=1/2*abs((x-x1)*(y3-y1)-(x3-x1)*(y-y1));
s3:=1/2*abs((x2-x)*(y3-y)-(x3-x)*(y2-y));
If s=s1+s2+s3 then writeln('Точка лежит внутри треугольника')
else writeln('Точка лежит вне треугольника');
end;
readkey;
end.

[Fuadik]

Можно ли за один рейс перевезти несколько грузов при условии, что их суммарный вес не превышает К?

[Ivanna]

Сообщение от Fuadik

Можно ли за один рейс перевезти несколько грузов при условии, что их суммарный вес не превышает К?

Может и можно

[Ivanna]

Сообщение от ROMA2PVT

{Задана точка с координатами (x, y) и треугольник с координатами
вершин(x1, y1) (x2, y2) (x3, y3).
Определить, лежит ли точка внутри или снаружи треугольника.}
Uses
  CRT;
var
  x,y,x1,x2,x3,y1,y2,y3:real;
  s,s1,s2,s3:real;
Begin
Clrscr;
write('Введите A: ');
readln(x1);
readln(y1);
write('Введите B: ');
readln(x2);
readln(y2);
write('Введите С: ');
readln(x3);
readln(y3);
write('Введите координаты точки: ');
readln(x);
readln(y);
If (x1=x2) and (x3=x1) or (y1=y2) and (y2=y3) then
write('Неверные координаты!')
else
begin
s:=1/2*abs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1));
s1:=1/2*abs((x2-x1)*(y-y1)-(x-x1)*(y2-y1));
s2:=1/2*abs((x-x1)*(y3-y1)-(x3-x1)*(y-y1));
s3:=1/2*abs((x2-x)*(y3-y)-(x3-x)*(y2-y));
If s=s1+s2+s3 then writeln('Точка лежит внутри треугольника')
else writeln('Точка лежит вне треугольника');
end;
readkey;
end.

А вы не знаете как развязать первую задачу?

[LeBron]

Первая задача в общем случае NP-полная. Это Set cover problem. Я не вижу здесь дополнительных ограничений, которые делают возможным полиномиальное решение. Но может оно и есть, так как я в этой области не очень хорошо разбираюсь Решение на битках уложить даже в сутки нереально.

Жадник можно легко завалить, так как он (как и все известные эвристики) не всегда дает правильный ответ.

Частный случай с номерами по порядку - простая симуляция.