Форум программистов, компьютерный форум CyberForum.ru

Центр тяжести - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 39, средняя оценка - 4.64
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
12.09.2011, 21:57     Центр тяжести #1
Горю!
По координатам вершин многоугольника требуется найти координаты его центра тяжести. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Площадь многоугольника не равна нулю.



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

В первой строке находится число 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 минут
КТО НИБУДЬ ЕСТЬ ТУТ???
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.09.2011, 21:57     Центр тяжести
Посмотрите здесь:

C++ Центр графа
Точка, наиболее близкая к центру тяжести C++
C++ Центр орграфа, классы
C++ Тело падает под действием силы тяжести
Центр симметрии C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
12.09.2011, 22:03     Центр тяжести #2
Не кричите. Центр тяжести многоугольника находится на пересечении его диагоналей.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
13.09.2011, 12:30  [ТС]     Центр тяжести #3
soon, а каких именно диагоналей? там их много, и они не пересекаются в одной точке
многоугольник неправильный
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
13.09.2011, 13:05     Центр тяжести #4
http://algolist.manual.ru/maths/geom...enter_mass.php
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
13.09.2011, 13:09     Центр тяжести #5
Хм... Я почему то думал только про выпуклые
Смотрите здесь. Внизу страницы есть исходный код и формула, по которой у нескольких выпуклых многоугольников(образующих неправильный многоугольник) находится общий центр тяжести.

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

Не по теме:

Опередили

AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
13.09.2011, 17:07  [ТС]     Центр тяжести #6
soon, многоугольник то выпуклый, только он не равносторонний. Если бы был правильный шестиугольник тогда да, а тут произвольный...

Добавлено через 1 минуту
Цитата Сообщение от soon Посмотреть сообщение
Смотрите здесь.
Эти решения неверные, я их тоже отправлял. Мне почему то казалось, что центр тяжести это есть центр масс, но это не так.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
13.09.2011, 17:12     Центр тяжести #7
Пфф. Это уж я дал маху.
Для _выпуклых_ но не равносторонних(хотя бы тот же прямоугольник) рассчитывается по формуле
X = (x1 + x2 + ... + xn)/N
Y = (y1 + y2 + ... + xn)/N

Добавлено через 1 минуту
Кстати, уверены что многоугольник именно выпуклый? В задании нигде(ну, я не увидел ) не указано, какой многоугольник.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
13.09.2011, 17:13  [ТС]     Центр тяжести #8
soon, 2 теста проходит та формула, она с того сайта что кинул до этого(((
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
13.09.2011, 17:16     Центр тяжести #9
Выложите, пожалуйста, непосредственно линк на задачу.

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

Не по теме:

Уже нашел

AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
13.09.2011, 17:20  [ТС]     Центр тяжести #10
многоугольник невыпуклый
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
13.09.2011, 17:36     Центр тяжести #11
Цитата Сообщение от AvengerAlive Посмотреть сообщение
soon, многоугольник то выпуклый, только он не равносторонний. Если бы был правильный шестиугольник тогда да, а тут произвольный...
Цитата Сообщение от AvengerAlive Посмотреть сообщение
многоугольник невыпуклый
Что взять за истину?
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
13.09.2011, 18:50  [ТС]     Центр тяжести #12
soon, второе
KuKu
 Аватар для KuKu
1539 / 1017 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
13.09.2011, 19:08     Центр тяжести #13
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Мне почему то казалось, что центр тяжести это есть центр масс, но это не так.
Центр масс и центр тяжести это не одно и тоже, если гравитационное поле неравномерное. Но это как мне кажется не ваш случай. У вас про поле ничего не сказано, значит это одно и тоже. Далее где распределена масса многоугольника ? - если в вершинах, то это совсем легко(это универсальная формула для системы равномассных точек):
Цитата Сообщение от soon Посмотреть сообщение
Пфф. Это уж я дал маху.
Для _выпуклых_ но не равносторонних(хотя бы тот же прямоугольник) рассчитывается по формуле
X = (x1 + x2 + ... + xn)/N
Y = (y1 + y2 + ... + xn)/N
Если по периметру, то формула в общем виде будет:
http://www.cyberforum.ru/cgi-bin/latex.cgi?\int \frac{m\vec{r}}{M}
В данном случае будет интеграл суммы = сумме интегралов. То есть вы находите центр масс каждой прямой, домножаете на массу каждой прямой(хм ... тут про массы у вас слов нет, так что умножайте на длину прямой), суммируйте все полученные величины и делите на общую массу(общую длину) и будет вам счастье. Конечно все эти действия надо произвести в проекции на обе оси.
http://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
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
13.09.2011, 20:08  [ТС]     Центр тяжести #14
KuKu, а для Y какая формула? Y и X местами поменять или как?
KuKu
 Аватар для KuKu
1539 / 1017 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
13.09.2011, 20:53     Центр тяжести #15
Да, поменяйте местами.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
13.09.2011, 21:39  [ТС]     Центр тяжести #16
на тесте
1 1
11 1
11 11
1 11
должно 6 выдавать, но не выдаёт.
KuKu
 Аватар для KuKu
1539 / 1017 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
14.09.2011, 08:47     Центр тяжести #17
На бумажке посчитайте вначале.
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
14.09.2011, 09:48     Центр тяжести #18
А что за задача, можно взглянуть на оригинал?

Не по теме:


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

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.09.2011, 17:22     Центр тяжести
Еще ссылки по теме:

Центр тяжести C++
Определить центр тяжести между точками C++
C++ Определить координаты точки наиболее близкой к центру тяжести

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
KuKu
 Аватар для KuKu
1539 / 1017 / 69
Регистрация: 17.04.2009
Сообщений: 2,946
14.09.2011, 17:22     Центр тяжести #19
Да в первом посте вродь суть написана, только непонятно где распределено вещество(в точка, по периметру или по площади). Про треугольники вроде не то, хотя может что-то не так понял.
Yandex
Объявления
14.09.2011, 17:22     Центр тяжести
Ответ Создать тему
Опции темы

Текущее время: 17:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru