Матч 253, Упаковка объектов (ObjectPacking)

Дивизион 2, Уровень 1

Имеется несколько коробок прямоугольной формы. Ширина i - ой коробки задается в ячейке boxWidth[i], длина – в boxLength[i]. Задан объект прямоугольной формы, ширина которого равна objWidth, а длина objLength. Необходимо найти коробку с наименьшей площадью, в которую можно поместить объект. Объект можно вращать на 0, 90, 180 или 270 градусов.

Класс: ObjectPacking

Метод: int smallBox(int objWidth, int objLength,

vector<int> boxWidth, vector<int> boxLength)

Ограничения: boxWidth и boxLength имеют одинаковую длину и содержат от 1 до 50 чисел, 1 £ objWidth[i], objLength[i], objWidth, objLength £ 1000.

Вход. Целые числа objWidth и objLength – размеры объекта, массивы boxWidth и boxLength, содержащие размеры коробок.

Выход. Наименьшая площадь коробки, в которую можно поместить объект. Если объект нельзя поместить ни в одну из имеющихся коробок, вернуть -1.

Пример входа

objWidth	objLength	boxWidth	boxLength
7	3	{3}	{7}
5	8	{6,9,3}	{7,4,5}
17	5	{19,10,12,40}	{12,20,15,5}
1	10	{9,1,10}	{10,6,4}

Пример выхода

21

-1

200

40

РЕШЕНИЕ

элементарные вычисления

Пусть ширина текущей коробки равна W, длина – L. Объект с размерами objWidth и objLength можно поместить в коробку, если выполняется условие

(W >= objWidth) && (L >= objLength)

или

(W >= objLength ) && (L >= objWidth)

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

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class ObjectPacking

{

public:

int smallBox(int objWidth, int objLength, vector<int> boxWidth,

vector<int> boxLength)

{

int W, L, i, res = 1000000000;

for(i = 0; i < boxWidth.size(); i++)

{

W = boxWidth[i]; L = boxLength[i];

if (((W >= objWidth) && (L >= objLength)) ||

((W >= objLength ) && (L >= objWidth)))

if (W * L < res) res = W * L;

}

return (res == 1000000000) ? -1 : res;

}

};