ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1246. Собака на привязи

2 coord?
Послано Evil Cheater 18 мар 2003 00:05
 Is it posible to solve it using only the first 2 coordinates? I
already found a solution but it uses 3 coordinates and I have to read
all coordinates first.
Hmm. My solution uses all vertices. Could you explain solution with 3 coords. Mine inside.
Послано Evil Hacker 18 мар 2003 00:59
For each line segment (x1; y1) (x2; y2) I calculate cross product of
2 vectors:
(0; 0) (x1; y1)   and (0; 0) (x2; y2)

Summing all cross products gives double square of polygon but with
one exception: it is positive if vertices are situated ccw and
negative otherwise (cw).
Re: Hmm. My solution uses all vertices. Could you explain solution with 3 coords. Mine inside.
Послано Evil Cheater 18 мар 2003 10:02
  Just look for the upper, the lower and the most to the right
points. Then label then acording on how you found them (e.g.: if you
find the lower first then you give it a lower number than the upper
point, I used "i" for this).

  Then you just have to check the sequence. If you have any problem
understanding this, I can post my solution.

PS: This algorithm has a small bug that you don't have to fix in
order to get AC!
What's the bug to this algorithm?
Послано ValBG 7 май 2003 00:46
Vallery777@yahoo.com
What about the sample input?
Послано ValBG 7 май 2003 01:36
   My program uses the following method:
   I choose the upper, lower and rightmost points and then sort them
in the order they were visited. Suppose their coordinates are
(x1,y1), (x2,y2), (x3,y3), where 1 was the first visited, 2 - second
and 3 - third.
   Then I put them in a martix
   x1 y1 1
   x2 y2 1
   x3 y3 1
and calculate D=x1*y2*1-x3*y2*1. If D>0, the 3 points are oriented
clockwise. When D<0, then orientation is counterclockwise.
   But what happens when D=0? And why is my method wrong for the
sample input?
   Pls help me!
   Vallery777@yahoo.com