Матч 432, Деление деревьев (TreesDivision)

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

Два брата в саду собирают фрукты. Сад является плоскостью, а деревья – точками на ней. Сад решено разбить прямой на две части так, чтобы ни одно дерево не находилось на ней. Первый брат собирает фрукты на одной стороне сада, второй – на другой. Прибыль, которую можно получить с i - го дерева с координатами (x[i], y[i]), составляет income[i]

Вычислить наименьшее возможное абсолютное значение разности прибылей братьев.

Класс: TreesDivision

Метод: int minDifference(vector<int> x, vector<int> y,

vector<int> income)

Ограничения: x и y содержат одинаковое количество элементов, от 2 до 50, 0 £ x[i], y[i] £ 1000, 0 £ income[i] £ 10⁶, все точки (x[i], y[i]) разные.

Вход. Массивы x и y, содержащие координаты деревьев в саду и массив прибыли income.

Выход. Наименьшее возможное абсолютное значение разности прибылей братьев.

Пример входа

x	y	income
{1,2}	{2, 3}	{10, 20}
{0,0,0,0,0}	{1,2,3,4,5}	{1,2,3,4,1000}
{4,2,4,2,3,6,3,5}	{1,2,4,3,3,2,4,5}	{4,5,2,6,7,4,2,4}

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

10

990

2

РЕШЕНИЕ

перебор + геометрия

Поскольку деревьев больше двух, то искомая прямая обязательно лежит между некоторыми двумя точками. Эту прямую можно двигать до тех пор, пока она не коснется некоторой точки, а потом вращать вокруг нее пока она не коснется другой точки. Таким образом, поиск прямой для разделения сада можно совершать перебирая прямые между всеми парами деревьев.

Прямая разделяет сад на две части. Прибыль с деревьев, находящихся по одну сторону от прямой, отдаем первому брату, а прибыль с деревьев по другую сторону – другому. Для определения стороны, по которую находится дерево от прямой, используем векторное произведение. Отдельно следует обработать деревья, находящиеся на текущей рассматриваемой прямой (в переменную in заносим прибыль с них). Это множество никогда не будет пустым, так как оно содержит как минимум два дерева, через которые проходит прямая. Отсортируем точки, находящиеся на прямой, по x координате (в случае равенства x координаты сортируем точки по y координате). Двигаемся по прямой, вычисляем сумму прибыли с деревьев в переменной s. На каждом шаге можно либо прибыль s отдать первому брату, а in – s второму, либо in – s первому, а s второму. В переменной res вычисляем модуль разности прибылей братьев.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

vector<int> v,xx,yy;

int f(int i, int j)

{

if (xx[i] == xx[j]) return yy[i] > yy[j];

return xx[i] > xx[j];

}

class TreesDivision

{

public:

int minDifference(vector<int> x, vector<int> y, vector<int> income)

{

int a, b, i, j, k, s, in, res = 1000000000;

xx = x; yy = y;

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

for(j = i + 1; j < x.size(); j++)

{

v.clear();

for(a = b = k = in = 0; k < x.size(); k++)

{

if ((x[j] - x[i]) * (y[k] - y[i]) > (x[k] - x[i]) * (y[j] - y[i]))

a += income[k]; else

if ((x[j] - x[i]) * (y[k] - y[i]) < (x[k] - x[i]) * (y[j] - y[i]))

b += income[k]; else

in += income[k],v.push_back(k);

}

sort(v.begin(),v.end(),f);

for(s = k =0 ;k < v.size(); k++)

{

s += income[v[k]];

// a + s ... b + in - s

res = min(res, abs(a + s - (b + in - s)));

// a + in - s ... b + s

res = min(res, abs(a + in - s - (b + s)));

}

}

return res;

}

};