[Logo] Форум DL
  [DL]  Back to home page 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Author Message
Ruslan Korzhik

Topics: 14
Messages: 86

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

Topics: 9
Messages: 30

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

Topics: 6
Messages: 37

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

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

2Edit: Ну и в чем была проблема?
http://www.spoj.pl/status/krishkinn,STONE/
______________________
Nothing is impossible; impossible itself says: "I m possible"...
Ruslan Korzhik

Topics: 14
Messages: 86

My Profile
+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: Вместо диагоналей написал первоначально, зачем-то, хорды. Исправился. Это наверное потому что думал над другой задачей, когда писал про эту.
Gennadiy Korotkevich

Topics: 6
Messages: 37

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

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

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

Topics: 14
Messages: 86

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

Topics: 0
Messages: 36

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

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

Topics: 14
Messages: 86

My Profile
Я проверял свой алгоритм на нескольких невыпуклых многоугольниках. Все работало. Получалось так, что треугольники с отрицательными площадями компенсировали лишние площади. Хотя возможно я "хорошие" тесты проверял.
 
Forum Index ->Олимпиадное программирование ->Обсуждение Sphere-задач
Time:0,094