10002. Центр
масс
Найти координаты центра масс
выпуклого многоугольника.
Вход. Состоит
из нескольких тестов. Первая строка каждого теста содержит количество вершин n (n ≤ 100) многоугольника. Следующие n
пар целых чисел описывают x и y координаты точек. Точки каждого многоугольника не
упорядочены. Многоугольник в последнем тесте содержит n < 3 вершин и не обрабатывается.
Выход. Для каждого многоугольника в
отдельной строке вывести координаты x и y центра масс.
Пример входа
4 0 1 1 1 0 0 1 0
3 1 2 1 0 0 0
7
-4 -4
-6 -3
-4 -10
-7 -12
-9 -8
-3 -6
-8 -3
1
Пример выхода
0.500 0.500
0.667 0.667
-6.102 -7.089
РЕШЕНИЕ
геометрия
Анализ алгоритма
Будем
считать, что масса равномерно распределена по области, ограниченной
многоугольником (то есть фигура вырезана из тонкого однородного материала). Тогда
имеет место теорема:
Теорема. Пусть
фигура Ф является объединением двух других фигур Ф1 и Ф2,
пересекающимися только по границе. Тогда центр тяжести фигуры Ф выражается так:
Xc = 
, Yc = 
, где
(Xc, Yc) – координаты
центра тяжести фигуры Ф;
(Xc1, Yc1) – координаты
центра тяжести фигуры Ф1;
(Xc2, Yc2) – координаты
центра тяжести фигуры Ф2;
S – площадь фигуры Ф, S1 – площадь фигуры Ф1, S2 –
площадь фигуры Ф2.
Кроме
того, для треугольника центр тяжести определяется так:
Xc = 
, Yc = 
,
Разобъем
многоугольник на треугольники. Для каждого треугольника найдем его центр
тяжести (xci, yci) и площадь si. Тогда координаты центра многоугольника
можно найти следующим образом:
Xc = 
, Yc = 
Здесь m равно количеству треугольников, на
которые разбит многоугольник.
Реализация алгоритма
Пусть пара p содержит координаты точки P. Пусть точка О – центр координат. Функция PolarAngle(p) возвращает значение полярного угла между вектором OP и осью OX, измеряемое в пределах от 0 до 
радиан.
double PolarAngle(pair<double,double> p)
{
double res =
atan2(1.0*p.second,1.0*p.first);
if (res <
0) res += 2*PI;
return res;
}
Функция f
используется при сортировке вершин многоугольника по полярному углу.
int f(pair<double,double> a, pair<double,double> b)
{
return
PolarAngle(a) < PolarAngle(b);
}
Функция
TriangleSquare(a, b, c)
вычисляет площадь треугольника, заданного координатами трех вершин.
double TriangleSquare(pair<double,double> a,
pair<double,double>
b,
pair<double,double> c)
{
return
abs((b.first - a.first) * (c.second - a.second) –
(c.first - a.first) * (b.second - a.second)) / 2.0;
}
Основная часть программы.
Координаты вершин очередного многоугольника
запоминаем в векторе пар v.
while(scanf("%d",&n), n > 2)
{
v.clear();
for(i = 0;
i < n; i++)
{
scanf("%d
%d",&a,&b);
v.push_back(make_pair(a,b));
}
Найдем координаты точки (NewXC, NewYC), лежащей
внутри многоугольника. Поскольку по условию задачи многоугольник выпуклый, то в
качестве такой точки можно взять центр тяжести треугольника, образованного
точками 0, 1 и 2.
NewXC = (v[0].first + v[1].first +
v[2].first) / 3.0;
NewYC = (v[0].second + v[1].second +
v[2].second) / 3.0;
Совершим параллельный перенос всех точек многоугольника на
вектор (–NewXC, –NewYC).
for(i = 0;
i < n; i++)
v[i].first -= NewXC, v[i].second -= NewYC;
Теперь начало координат (0, 0) находится внутри выпуклого
многоугольника. Сортируем вершины многоугольника по полярному углу.
sort(v.begin(),v.end(),f);
Разобъем исходный многоугольник на треугольники с
вершинами (0, i, i + 1), 
. Для каждого такого тругольника вычисляем его площадь в
переменной tempSquare, а также
координаты его центра. Последние прибавляем к переменным xc и yc, умножая их
предварительно на tempSquare. В
переменной s накапливаем
площадь всего многоугольника.
xc = yc = s = 0;
for(i = 1;
i < n - 1; i++)
{
tempSquare =
TriangleSquare(v[0],v[i],v[i+1]);
s += tempSquare;
xc += tempSquare * (v[0].first +
v[i].first + v[i+1].first) / 3.0;
yc
+= tempSquare * (v[0].second + v[i].second + v[i+1].second) / 3.0;
}
Разделив полученные значения xc и yc на s и сдвинув их на вектор (NewXC, NewYC), получим
координаты центра масс исходного многоугольника.
xc = xc / s + NewXC; yc = yc / s + NewYC;
if
(fabs(xc) < 0.00001) xc = 0.0;
if
(fabs(yc) < 0.00001) yc = 0.0;
Выводим координаты центра масс.
printf("%.3lf
%.3lf\n",xc,yc);
}