Форум DL

Мой профиль

Кто нибудь эту задачу сдал? Там нет никаких заморочек с выводом? На DL эта задача у меня прошла, а там WA

Мой профиль

Хм.. У меня тоже не сдаеться... У тебя такое решение:
Бил на треугольники. Далее масса = площадь треугольника. Центр треуголника - пересечение медиан. Далее просто центр тяжести
(x1*m1+x2*m2...xn*mn)/(m1+m2+...+mn)

Мой профиль

А как ты бил на треугольники?
Многоугольник по условию не обязательно выпуклый...

Edit: Могут быть и заморочки с выводом -0.00, попробуйте добавлять к ответу епсилон...

2Edit: Ну и в чем была проблема?

http://www.spoj.pl/status/krishkinn,STONE/
______________________
Nothing is impossible; impossible itself says: "I m possible"...

Мой профиль

+eps помогло. А на DL прошло, потому что компилятор другой был.

Спасибо.

Решение такое же как у Вовы(наверное). Только не уверен на счет центра тяжести треугольника. Я искал его так Xc=(x1+x2+x3)/3. Не знаю будет ли это пересечение медиан.
Идея решения:
Из первой вершины проводим диагонали во все остальные.
Затем удвоенную площадь получившихся треугольников ищем по формуле:
(x1-x2)*(y1+y2)+(x2-x3)*(y2+y3)+(x3-x1)*(y3+y1)
Как видно из формулы площадь может быть и отрицательная.
Затем по аналогичной формуле ищем удвоенную площадь всей фигуры (тоже без модуля).
После этого центр тяжести ищем по формуле:
Xc=(Xc1*S1+Xc2*S2....)/S

Xci,Yci - центр i-того треугольника
Si - площадь i-того треугольника(со знаком)
S - площадь всей фигуры(со знаком)

Edit: Вместо диагоналей написал первоначально, зачем-то, хорды. Исправился. Это наверное потому что думал над другой задачей, когда писал про эту.

Мой профиль

По-моему, многоугольник по условию необязательно выпуклый...
Или если проводить диагонали из любой вершины, это все равно будет правильно?

Edit: А насчет центра тяжести - насколько я знаю, правильная формула Xc = (x1+x2+x3)/3.

2Edit: Сдал я эту задачу

Как оказалось, разбивать на треугольники можно даже так: взять точку X = (x1+x2+..+xn)/n и из нее проводить диагонали. Получается, что многоугольник обязательно выпуклый. Странно...
______________________
Nothing is impossible; impossible itself says: "I m possible"...

Мой профиль

А площади брал со знаком?

Мой профиль

От Геннадия Короткевича

:

Всегда брал положительную с absом. А что?

Мой профиль

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