Матч 272, Многоугольник из векторов (VectorPolygon)

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

Имеется набор векторов, координаты которых хранятся в массивах dx и dy (i - ый вектор имеет координаты (dx[i], dy[i])). Необходимо выбрать такое подмножество векторов, из которых можно составить выпуклый многоугольник наибольшей площади. Если выпуклого многоугольника составить нельзя, то вывести 0.0.

Класс: VectorPolygon

Метод: double maxArea(vector<int> dx, vector<int> dy)

Ограничения: dx и dy содержат от 1 до 8 элементов, длины векторов dx и dy одинаковы, -100 £ dx[i], dy[i] £ 100, все вектора ненулевые.

Вход. Координаты векторов, заданные в массивах dx и dy.

Выход. Площадь максимально возможного многоугольника, составленного из некоторого подмножества заданных векторов. Если такого многоугольника не существует, вывести 0.0.

Пример входа

dx	dy
{2,3,-5}	{2,-4,2}
{2,-3,-5}	{2,4,2}
{0,0,1,-1}	{1,-1,0,0}
{25,50,75,100,-25,-50,-75,-100}	{100,75,50,25,-100,-75,-50,-25}
{100}	{-100}

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

7.0

0.0

1.0

31250.0

0.0

РЕШЕНИЕ

полный перебор + сортировка + геометрия

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

Отсортируем сначала вектора по углу с осью абсцисс. Генерируем все подмножества векторов, для каждого из которых находим сумму. Если сумма векторов равна нулю (многоугольник можно построить), то ищем площадь полученного выпуклого многоугольника по формуле трапеций (углы векторов любого подмножества будут отсортированы). Остается среди всех построенных таким образом многоугольников найти максимальную площадь.

Функция PolarAngle(p) вычисляет полярный угол вектора p с осью абсцисс. Угол имеет значение в пределах от 0 до 2π.

Функция f является функцией сортировки векторов по возрастанию полярного угла.

Функция GetArea(v) вычисляет площадь выпуклого многоугольника, составленного из набора векторов, содержащихся в v.

В массиве temp перебираем все подмножества исходного множества векторов.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cmath>

#define PI acos(-1.0)

using namespace std;

vector<pair<int,int> > v,temp;

double PolarAngle(pair<int,int> p)

// p != (0,0)

{

double res = 0;

int x = p.first, y = p.second;

if (x == 0)

{

if (y > 0)res = PI / 2; else res = 3*PI/2;

}

else

{

res = atan(1.0 * y / x);

if (x < 0) res = res + PI;

if (res < 0) res = res + 2 * PI;

}

return res;

}

// vectors (v[i].first,v[i].second) are sorted by angle to Ox

// [0... 2*PI]

int f(pair<int,int> a, pair<int,int> b)

{

return PolarAngle(a) < PolarAngle(b);

}

double GetArea(vector<pair<int,int> > &v)

{

double s;

int i;

v.push_back(v[0]); v[0] = make_pair(0,0);

for(i = 1; i < v.size(); i++)

v[i].first = v[i-1].first + v[i].first,

v[i].second = v[i-1].second + v[i].second;

for(s = i = 0; i < v.size() - 1; i++)

s += (v[i+1].second + v[i].second) * (v[i+1].first - v[i].first);

return fabs(s) / 2.0;

}

class VectorPolygon

{

public:

double maxArea(vector<int> dx, vector<int> dy)

{

int i, j, c, cx, cy, n = dx.size();

double area, res = 0;

for(i = 0; i < n; i++) v.push_back(make_pair(dx[i],dy[i]));

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

for(i = 1; i < (1<<n); i++)

{

// temp contains the subset of vectors

temp.clear();

for(c = 0, j = i; j > 0; j /= 2, c++)

if (j&1) temp.push_back(v[c]);

// With less than 3 vectors we can't make polygon

if (temp.size() < 3) continue;

// Find sum of vectors

for(cx = 0, cy = 0, j = 0; j < temp.size(); j++)

cx += temp[j].first, cy += temp[j].second;

if ((cx != 0) || (cy != 0)) continue;

// Find the polygon area

area = GetArea(temp);

if (area > res) res = area;

}

return res;

}

};