Центр тяжести

@AvengerAlive · Регистрация: 30.07.2011

Студворк — интернет-сервис помощи студентам

Горю!
По координатам вершин многоугольника требуется найти координаты его центра тяжести. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Площадь многоугольника не равна нулю.

Технические условия
Входные данные

В первой строке находится число N, в следующих N строках - пары чисел - координаты точек. Если соединить точки в данном порядке, а также соединить первую и последнюю точки, получится заданный многоугольник.

Число вершин 3 ≤ N ≤ 100000, координаты вершин в декартовой системе координат целые и по модулю не превосходят 20000.

Выходные данные

Вывести два числа с двумя знаками после запятой - координаты центра тяжести

Пример входных данных
Sample 1
4
5 0
0 5
-5 0
0 -5

Sample 2
4
1 1
11 1
11 11
1 11

Пример выходных данных
Sample 1
0.00 0.00

Sample 2
6.00 6.00

Прошёл всего 2 теста из 5ти. Пробовал ещё на всякий случай сортировать вершины в поряд обхода, вдруг в тестах не так что-то, не помогает.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
 
struct pt {
  double x, y;
};
 
bool cmp (pt a, pt b) {
  return a.x < b.x || a.x <= b.x && a.x >= b.x && a.y < b.y;
}
 
bool cw (pt a, pt b, pt c) {
  return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}
 
bool ccw (pt a, pt b, pt c) {
  return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}
 
double dist(pt a, pt b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
 
double geron(pt a, pt b, pt c)
{
double p,a1,a2,a3;
a1=dist(a,b);
a2=dist(b,c);
a3=dist(a,c);
p=a1+a2+a3;
p/=2;
return sqrt(p*(p-a1)*(p-a2)*(p-a3));
}
 
int main()
{
pt a[100001];
int n,i;
double s,x0,y0,x1,y1,s1;
scanf("%d",&n);
  s=0; x0=0; y0=0;
  for (i=0; i<n; i++)
   {
    scanf("%lf%lf",&a[i].x,&a[i].y);
   }
  for (i=1; i<n; i++)
   {
    s1=geron(a[0],a[i-1],a[i]);
    s+=s1;
    x1=a[0].x+a[i-1].x+a[i].x;
    y1=a[0].y+a[i-1].y+a[i].y;
    x0+=((x1*s1)/3.0);
    y0+=((y1*s1)/3.0);
   }
  cout << fixed << setprecision(2) << x0/s << " " << y0/s << endl;
return 0;
}

Помогите найти ошибку!

Добавлено через 1 час 8 минут
Пишите кто знает как решается задача!

Добавлено через 2 часа 7 минут
КТО НИБУДЬ ЕСТЬ ТУТ???

@soon · 12.09.2011, 22:03

Не кричите. Центр тяжести многоугольника находится на пересечении его диагоналей.

@AvengerAlive · 13.09.2011, 12:30 **[ТС]**

soon, а каких именно диагоналей? там их много, и они не пересекаются в одной точке
многоугольник неправильный

@Deviaphan · 13.09.2011, 13:05

http://algolist.manual.ru/math... r_mass.php

@soon · 13.09.2011, 13:09

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

Добавлено через 49 секунд

Не по теме:

http://algolist.manual.ru/math... r_mass.php

Опередили :)

@AvengerAlive · 13.09.2011, 17:07 **[ТС]**

soon, многоугольник то выпуклый, только он не равносторонний. Если бы был правильный шестиугольник тогда да, а тут произвольный...

Добавлено через 1 минуту

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

Смотрите здесь.

Эти решения неверные, я их тоже отправлял. Мне почему то казалось, что центр тяжести это есть центр масс, но это не так.

@soon · 13.09.2011, 17:12

Пфф. Это уж я дал маху.
Для _выпуклых_ но не равносторонних(хотя бы тот же прямоугольник) рассчитывается по формуле
X = (x1 + x2 + ... + xn)/N
Y = (y1 + y2 + ... + xn)/N

Добавлено через 1 минуту
Кстати, уверены что многоугольник именно выпуклый? В задании нигде(ну, я не увидел

) не указано, какой многоугольник.

@AvengerAlive · 13.09.2011, 17:13 **[ТС]**

soon, 2 теста проходит та формула, она с того сайта что кинул до этого(((

@soon · 13.09.2011, 17:16

Выложите, пожалуйста, непосредственно линк на задачу.

Добавлено через 55 секунд

Не по теме:

Уже нашел ;)

@AvengerAlive · 13.09.2011, 17:20 **[ТС]**

многоугольник невыпуклый

@soon · 13.09.2011, 17:36

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

soon, многоугольник то выпуклый, только он не равносторонний. Если бы был правильный шестиугольник тогда да, а тут произвольный...

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

многоугольник невыпуклый

Что взять за истину?

@AvengerAlive · 13.09.2011, 18:50 **[ТС]**

soon, второе

KuKu · 13.09.2011, 19:08

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

Мне почему то казалось, что центр тяжести это есть центр масс, но это не так.

Центр масс и центр тяжести это не одно и тоже, если гравитационное поле неравномерное. Но это как мне кажется не ваш случай. У вас про поле ничего не сказано, значит это одно и тоже. Далее где распределена масса многоугольника ? - если в вершинах, то это совсем легко(это универсальная формула для системы равномассных точек):

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

Пфф. Это уж я дал маху.
Для _выпуклых_ но не равносторонних(хотя бы тот же прямоугольник) рассчитывается по формуле
X = (x1 + x2 + ... + xn)/N
Y = (y1 + y2 + ... + xn)/N

Если по периметру, то формула в общем виде будет:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\int \frac{m\vec{r}}{M}$
В данном случае будет интеграл суммы = сумме интегралов. То есть вы находите центр масс каждой прямой, домножаете на массу каждой прямой(хм ... тут про массы у вас слов нет, так что умножайте на длину прямой), суммируйте все полученные величины и делите на общую массу(общую длину) и будет вам счастье. Конечно все эти действия надо произвести в проекции на обе оси.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?Xc = \frac{\sum_{i=0}^{n}\frac{{X}_{i+1}+{X}_{i}}{2}\sqrt{({X}_{i+1}-{X}_{i})^2+({Y}_{i+1}-{Y}_{i})^2}}{\sum_{i=0}^{n}\sqrt{({X}_{i+1}-{X}_{i})^2+({Y}_{i+1}-{Y}_{i})^2}}$
Такую бяку в общем посчитайте и аналогично для Y. Вроде нигде не ошибся, хотя кто его знает)

@AvengerAlive · 13.09.2011, 20:08 **[ТС]**

KuKu, а для Y какая формула? Y и X местами поменять или как?

KuKu · 13.09.2011, 20:53

Да, поменяйте местами.

@AvengerAlive · 13.09.2011, 21:39 **[ТС]**

на тесте
1 1
11 1
11 11
1 11
должно 6 выдавать, но не выдаёт.

KuKu · 14.09.2011, 08:47

На бумажке посчитайте вначале.

@#pragma · 14.09.2011, 09:48

А что за задача, можно взглянуть на оригинал?

Не по теме:

Это случайно не про кратчайшие пути между множеством точек? Просто стало любопытно, ведь если так, то тогда все произвольные фигуры , вроде бы, нужно сначала разделить на самые простые - треугольники, а уже после этого искать все центры тяжести в них, и соединять между собой. Там получается рисунок по аналогии форм пузырей мыльной пены между двумя пластинами. Если не в тему, то чур я не выспался :-|

KuKu · 14.09.2011, 17:22

Да в первом посте вродь суть написана, только непонятно где распределено вещество(в точка, по периметру или по площади). Про треугольники вроде не то, хотя может что-то не так понял.

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	12.09.2011, 22:03
	Не кричите. Центр тяжести многоугольника находится на пересечении его диагоналей. 1

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	13.09.2011, 12:30 [ТС]
	soon, а каких именно диагоналей? там их много, и они не пересекаются в одной точке многоугольник неправильный 0

@Deviaphan Делаю внезапно и красиво 1313 / 1228 / 72 Регистрация: 22.03.2011 Сообщений: 3,744
	13.09.2011, 13:05
	http://algolist.manual.ru/math... r_mass.php 0

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	13.09.2011, 17:12
	Пфф. Это уж я дал маху. Для _выпуклых_ но не равносторонних(хотя бы тот же прямоугольник) рассчитывается по формуле X = (x1 + x2 + ... + xn)/N Y = (y1 + y2 + ... + xn)/N Добавлено через 1 минуту Кстати, уверены что многоугольник именно выпуклый? В задании нигде(ну, я не увидел ) не указано, какой многоугольник. 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	13.09.2011, 17:13 [ТС]
	soon, 2 теста проходит та формула, она с того сайта что кинул до этого((( 0

@soon 2554 / 1319 / 178 Регистрация: 09.05.2011 Сообщений: 3,086 Записей в блоге: 1
	13.09.2011, 17:16
	Выложите, пожалуйста, непосредственно линк на задачу. Добавлено через 55 секунд Не по теме: Уже нашел ;) 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	13.09.2011, 17:20 [ТС]
	многоугольник невыпуклый 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	13.09.2011, 18:50 [ТС]
	soon, второе 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	13.09.2011, 20:08 [ТС]
	KuKu, а для Y какая формула? Y и X местами поменять или как? 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	13.09.2011, 20:53
	Да, поменяйте местами. 0

@AvengerAlive 5 / 5 / 1 Регистрация: 30.07.2011 Сообщений: 257
	13.09.2011, 21:39 [ТС]
	на тесте 1 1 11 1 11 11 1 11 должно 6 выдавать, но не выдаёт. 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	14.09.2011, 08:47
	На бумажке посчитайте вначале. 0

@#pragma Временно недоступен 957 / 228 / 14 Регистрация: 12.04.2009 Сообщений: 926
	14.09.2011, 09:48
	А что за задача, можно взглянуть на оригинал? Не по теме: Это случайно не про кратчайшие пути между множеством точек? Просто стало любопытно, ведь если так, то тогда все произвольные фигуры , вроде бы, нужно сначала разделить на самые простые - треугольники, а уже после этого искать все центры тяжести в них, и соединять между собой. Там получается рисунок по аналогии форм пузырей мыльной пены между двумя пластинами. Если не в тему, то чур я не выспался :-\| 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	14.09.2011, 17:22
	Да в первом посте вродь суть написана, только непонятно где распределено вещество(в точка, по периметру или по площади). Про треугольники вроде не то, хотя может что-то не так понял. 1