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

@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

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

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

@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